








           Balcaniada de Informatic[ este un concurs anual organizat la iniiativa
Romniei. Sistemul de desf[urare este similar celui de la Olimpiadele Interna-
ionale. Pot participa [rile din zona Balcanilor, plus invitai ai organizatorilor (de
exemplu, la prima ediie a participat i echipa Moldovei). 


           Ediia I (Constana, Romnia) - mai 1993

            BOI.1.(Obiecte). Consider[m un tablou bidimensional A cu m linii i n
coloane (1m19,1n19) ale c[rui elemente sunt 0 i 1. 0 reprezint[ fondul
(paper), 1 reprezint[ culoarea tuului (ink).
           Pe tablou sunt reprezentate mai multe obiecte. Prin obiect vom nelege o
mulime de elemente cu acelai ink (1), fiecare element avnd cel puin un vecin
n stnga, dreapta, sus, jos sau pe una din diagonale. Orice dou[ obiecte sunt
separate prin elemente de tipul 0 (paper).
           a) S[ se determine dreptunghiul de arie minim[ care conine un obiect
maximal (avnd cel mai mare num[r de elemente 1).
           b) S[ se plaseze obiectul aflat la punctul (a) n zonele tabloului care nu sunt
ocupate de alte obiecte, n aa fel nct copierea lui s[ se poat[ face n ct mai
multe locuri posibile f[r[ a distruge celelalte obiecte deja plasate.
Exemplu:
                                                       0  0  0  0  0  0  0  1  1  0
                                                          0  1  0  0  1  1  0  1  1  1     obiect
                                                          0  0  1  0  1  1  0  0  0  1
                                                          0  0  0  0  1  1  1  0  0  1
                                                          0  0  1  1  1  1  1  0  0  0
                                                          0  0  1  1  1  1  1  0  1  1
obiect maximal             1  1  1  1  1  0  0  0  1  1
                                                          0  0  0  1  0  0  0  0  1  1
                                                          0  0  0  0  0  0  0  0  0  0
                                                          0  0  0  0  0  0  0  0  0  0
                                                          0  0  0  0  0  0  0  0  0  0
                                                          0  0  0  0  0  0  0  0  0  0
                                                          0  0  0  0  0  0  0  0  0  0

                                                          plasare posibil[

                      BOI.2. (MasterMind). Intre calculator i tine se joac[ urm[torul joc:
Tu te gndeti la o secven[ de 4 culori (nu neap[rat distincte) alese dintr-o
mulime de ase culori posibile.
Calculatorul (programul t[u) trebuie s[ afle aceast[ secven[ folosind informaia
pe care o poate extrage din r[spunsul obinut la ntreb[ri de tipul 
                                  Secvena este.. ?
Tu vei r[spunde la ntreb[rile calculatorului dup[ fiecare secven[ nou generat[.
R[spunsul la o ntrebare a calculatorului conine dou[ p[ri:
a) Cte culori sunt corecte dar nu sunt aezate pe poziiile lor;
b) Cte culori sunt aezate pe poziiile corecte.
Exemplu: S[ presupunem c[ secvena c[utat[ este 4655. Un mod posibil de a afla
aceast[ secven[ este:
           Intrebarea calculatorului                R[spunsul t[u
                             1 2 3 4                a) 1b) 0
                               5 1 5 6              a) 2b) 1
                               6 1 6 5              a) 1b) 1
                               5 6 2 5              a) 1b) 2
                               5 6 5 3              a) 1b) 2
                               4 6 5 5              a) 0b) 4
1) Aflai o secven[ corect[ de ntreb[ri pentru a rezolva problema;
2) Aflai, dac[ este posibil, o soluie n maxim 6 ntreb[ri.


           BOI.3. (Lan aditiv). O secven[ de numere ntregi pozitive a1,a2,
..,an se numete lan aditiv de lungime n dac[, pentru orice k(1<kn), exist[
i i j, 1ij<k n aa fel ca ak=ai+aj. Scriei un program care, pentru a1=1
i ultimul element citit de la intrare, g[sete un lan aditiv de lungime minim[.
Exemplu: Pentru intrarea
4
un r[spuns posibil poate fi
1 2 4


            BOI.4. (Petrecere). Imaginai-v[ c[ luai parte la o serat[ la care
particip[ cel mult 500 persoane. Gazda i invit[ pe toi la cin[. In sufragerie
exist[ mai multe mese. Invitaii se aeaz[ la mas[ n felul urm[tor: fiecare
persoan[ care nu st[ singur[ la mas[ trebuie s[ cunoasc[ cel puin o persoan[
de la masa respectiv[. Se presupune c[ dac[ o persoan[ o cunoate pe a doua,
atunci i a doua o cunoate pe prima.
           Aezarea la mas[ nu este nsoit[ de prezent[ri. Drept urmare, dac[ dou[
persoane situate la aceeai mas[ nu se cunoteau iniial, ele nu se vor cunoate nici
dup[ aezarea la mas[.
a) Determinai num[rul minim de mese necesare i persoanele care sunt aezate la
fiecare mas[.
           La fiecare mas[ exist[ o singur[ persoan[ care va vorbi cu chelnerul;
aceast[ persoan[ este numit[ liderul mesei. Fiecare persoan[ transmite tuturor
persoanelor cunoscute situate la mas[, opiunea sa privind meniul. Timpul necesar
fiec[rei persoane de a transmite opiunea sa tuturor persoanelor pe care le cunoate
este constant[ i aceeai pentru fiecare persoan[.
b) Determinai pentru fiecare mas[ persoana cea mai indicat[ ca lider, astfel nct
aceasta s[ primeasc[ opiunile n timp minim; listai pentru fiecare mas[ liderul
ales i timpul corespunz[tor.
           Dup[ servirea cinei, gazda dorete s[ uneasc[ mesele. In acest scop, ea
cheam[ civa prieteni. Fiecare dintre acetia, la sosirea sa, este prezentat liderilor
a dou[ mese, dup[ care mesele sunt unite formnd o nou[ mas[.
c) Care este ordinea de unire a meselor astfel nct n final toate mesele s[ fie unite
ntr-una singur[ iar condiiile de la punctul (b) s[ r[mn[ satisf[cute ? Specificai
timpul minim necesar liderului mesei finale pentru a primi informaii de la toate
celelalte persoane.
           Dup[ unirea meselor, prietenii gazdei se retrag i mesele i recap[t[ struc-
tura dinainte de unire, pn[ la terminarea seratei. Cnd petrecerea se termin[,
persoanele ncep s[ p[r[seasc[ mesele.
d) Determinai, pentru fiecare mas[, num[rul minim de persoane i ordinea n care
acestea p[r[sesc masa, pn[ cnd persoanele care au r[mas la mas[ s[ nu se
cunoasc[ ntre ele.
Exemplu: S[ presupunem c[ num[rul persoanelor este 8 i c[:
- persoana 1 cunoate persoanele 2 i 3;
- persoana 2 cunoate persoanele 1 i 4;
- persoana 3 cunoate persoanele 1 i 4;
- persoana 4 cunoate persoanele 2 i 3;
- persoana 5 cunoate persoana 6;
- persoana 6 cunoate persoanele 5 i 7;
- persoana 7 cunoate persoana 6;
- persoana 8 nu cunoate nici o alt[ persoan[;
Un set corect de date are forma:
8
1  2
1  3
2  4
7  6
4  3
5  6
0  0
O ieire corect[ are forma:
  a)
3 mese
Masa 1: 1 2 3 4
Masa 2: 5 6 7
Masa 3: 8
  b)
Lideri:
Masa 1: 2; timp=2
Masa 2: 6; timp=1
Masa 3: 8; timp=0
  c)
6  8 Noul lider: 9
2  9 Noul lider: 10
Timp=3
  d)
Persoanele care pleac[:
Masa 1: 2  3
Masa 2: 6
Masa 3:


            Ediia II (Salonic, Grecia) -  oct. 1994

            BOI.5. (Numere Fibonacci prime). S[ se listeze toate numerele prime
x (10x65535) care:
 i. Sunt numere Fibonacci, i
ii. Permutnd cifrele lui x se obine cel puin nc[ un num[r prim distinct.
           Ieirea va consta dintr-un num[r de linii egal cu num[rul de elemente
existent. Fiecare linie va conine num[rul x urmat - dup[ un spaiu - de num[rul
prim obinut din x printr-o permutare a cifrelor.
Exemplu: Ieirea va ncepe astfel:
13 31
.....
Indicaie: Secvena de numere Fibonacci se construiete dup[ regula:
F0=0,F1=1,Fi=Fi-1+Fi-2, zi2.


            BOI.6. (Reea de calculatoare). Se dorete legarea n reea a n calcula-
toare (2n10). Problema const[ n obinerea unei reele liniare n care fiecare
calculator este legat exact de alte dou[ calculatoare, exceptnd calculatoarele din
capete, care au o singur[ leg[tur[. De exemplu, n desenul de mai jos calculatoa-
rele sunt identificate prin coordonatele lor (relativ la un sistem de axe neprecizat).
           Scopul problemei const[ n minimizarea lungimii cablului folosit; se cere
deci determinarea unui mod optim de reconectare al calculatoarelor n linie astfel
nct cablul folosit s[ aib[ lungimea minim[. Necesarul de cablu pentru a lega
direct dou[ calculatoare este egal cu distana dintre acestea, la care se adaug[ 10
m de cablu, utilizai pentru conexiuni anexe.












Intrare: Fiierul de intrare va reprezenta un set de date. Prima linie const[ dintr-un
singur num[r n (num[rul de calculatoare). In continuare, pe n linii succesive se dau
coordonatele fiec[rui calculator sub forma unei perechi de numere ntregi (din
intervalul [0,100]) separate prin cel puin un spaiu. De exemplu:
5
8 11
8 16
12 16
13 8
24 10
In acest caz reeaua are forma grafic[ prezentat[ mai sus, iar modul optim de
reconectare al calculatoarelor este:














Ieirea const[ din n linii. Pe prima linie se va da lungimea total[ a cablului.
Fiecare din celelalte linii este format[ din trei numere l,s,e avnd semnificaia:
lungimea l a cablului este necesar[ leg[rii directe a calculatoarelor definite la
intrare pe liniile s respectiv e. Ordinea de parcurgere a reelei este arbitrar[.
Pentru reeaua din exemplu ieirea va fi:
66.01
14     3 2
15     2 1
15.83  1 4
21.18  4 5


            BOI.7. (Sortare). Tehnica recicl[rii sticlei solicit[ ca sticla recuperat[ de
la populaie s[ fie separat[ dup[ culoare n trei categorii: maro, verde i incolor[.
Sunt date ordonat trei containere, fiecare avnd un num[r specificat de sticle maro,
verzi i incolore. Pentru a putea fi reciclate, sticlele trebuiesc mutate astfel ca n
final fiecare container s[ conin[ sticle de o singur[ culoare. Problema const[ n
minimizarea num[rului de mut[ri ale sticlelor (cte una), n ipoteza c[ toate
containerele au capacitate infinit[.
           Pe prima linie a fiierului de intrare este un num[r care specific[ num[rul
de linii (teste) succesive. Pe fiecare din aceste linii se afl[ nou[ numere separate
de cte un spaiu; primele trei reprezint[ num[rul de sticle maro, verzi i respectiv
incolore din containerul 1, urm[toarele trei numere pe cele din containerul 2, iar
ultimele trei, pe cele din containerul 3.
           Pentru fiecare linie de intrare se va afia o linie cu structura:
a) un ir format din caracterele B,G,C (culorile maro, verde, incolor) reprezentnd
n ordine coninutul fiec[ruia din cele trei containere;
b) un ntreg reprezentnd num[rul minim de mut[ri ale sticlelor.
Atenie: dac[ exist[ mai multe soluii optime, se afieaz[ numai soluia care este
prima n ordonarea alfabetic[ (dac[ soluiile ar fi GBC 18 i CGB 18, s-ar afia
numai CGB 18).
Exemple:
i) Intrare:
1 2 3 4 5 6 7 8 9
Ieire:
BCG 30
ii) Intrare:
5 10 5 20 10 5 10 20 10
Ieire:
CBG 50



                      BOI.8. (Model). Se d[ un tablou de dimensiune nxn (n10) ale c[rui
elemente sunt numere naturale x (1<x40).
a) In tablou se nlocuiete fiecare num[r x cu y=f(x) unde y este num[rul maxim
de numere prime cu suma x; n aceast[ sum[, fiecare num[r prim apare o singur[
dat[, exceptnd un singur num[r prim care poate s[ apar[ de dou[ ori. Se
consider[ c[ 1 nu este num[r prim. De exemplu:
2=2                                                                            f(2)=1
3=3                                                                        f(3)=1
4=2+2                                                                f(4)=2
5=3+2                                                                f(5)=2
6=3+3                                                                f(6)=2
7=3+2+2                                                     f(7)=3
.....                                                                ......
12=5+3+2+2                                            f(12)=4
           S[ se listeze tabloul rezultat.
b) Dup[ ce fiecare element x a fost nlocuit n tablou cu y=f(x), s[ se determine
num[rul maxim de elemente y care formeaz[ o arie compact[ (conex[) avnd n
vedere vecin[t[ile pe orizontal[, vertical[ i diagonal[ (dac[ y nu este unic cu
aceast[ proprietate, se alege cel mai mic). Precizai aceast[ valoare a lui y i
determinai dreptunghiul cel mai mic (avnd laturile paralele cu axele de coordonate)
care acoper[ aceast[ arie, afind coordonatele (linie, coloan[) pentru cel mai din
stnga-sus vrf i cel mai din dreapta-jos vrf.
c) In general, aria determinat[ la (b) nu este dreptunghi sau p[trat. S[ se determine
num[rul minim de p[trate de laturi diferite (1x1,2x2,3x3, etc.) cu care se poate
pava aria.
d) S[ se ncerce maximizarea ariei determinate la (b) efectund un num[r minim
de permut[ri n tabela rezultat[ la punctul (a). La ieire se vor da coordonatele
elementelor care se interschimb[ precum i noua tabel[ obinut[.
e) S[ se determine elementul y care apare de cele mai multe ori n tabela rezultat[
la punctul (a); dac[ dou[ sau mai multe elemente y au aceeai valoare, se alege
elementul y de valoare minim[. Se cere compactarea acestor elemente (prin conexi-
uni orizontale, verticale sau oblice) folosind un num[r minim de interschimb[ri. Se
cer coordonatele elementelor care se permut[ precum i noua tabel[ obinut[. 
Atenie: Tabela de plecare este cea obinut[ la punctul (a).
Intrare: Pe prima linie se afl[ un singur num[r n. Tabela se d[ pe urm[toarele n
linii, elementele de pe o linie fiind separate prin cel puin un spaiu; de exemplu:
6
19 20 12 13 14 22
23 14  7 15 16  8
 2  4  9 10 17 24
25 18 21 18 17 26
28 28 29 32  5 34
35  6 36  5 16 32
Ieire:
a) Dup[ nlocuirea fiec[rui x cu f(x), listarea primei ieiri din exemplu este:
5 5 4 4 4 5
5 4 3 4 4 3
1 2 3 3 4 5
5 4 4 4 4 5
5 5 5 5 2 5
6 2 6 2 4 5

b) Ieirea este dat[ pe trei linii separate, astfel:
11-                          reprezint[ num[rul maxim de elemente y aflate n conexiune;
4-                            valoarea lui y;
(2,1),(5,4)  - coordonatele dreptunghiului minim care acoper[ aria;

c) Ieirea const[ dintr-un singur num[r:
8-                            num[rul minim de p[trate care paveaz[ aria de la (b);

d) Ieirea va ar[ta astfel:
1-                                                     num[rul minim de permut[ri;
(5,5),(6,5)-                coordonatele elementelor permutate;
5 5 4 4 4 5
5 4 3 4 4 3
1 2 3 3 4 5
5 4 4 4 4 5
5 5 5 5 4 5
6 2 6 2 2 5
e) Ieirea va ar[ta astfel:
5-                                                     elementul de frecven[ maxim[;
2-                                                     num[rul minim de permut[ri;
(1,2),(3,1)
(1,6),(5,5)-                 permut[rile efectuate;
5 1 4 4 4 2
5 4 3 4 4 3
5 2 3 3 4 5
5 4 4 4 4 5
5 5 5 5 5 5
6 2 6 2 4 5

Atenie: Programul va ncepe cu ntrebarea:
                         "Dorii rezolvarea punctului (a) ?"

           Dac[ r[spunsul este DA, programul continu[ cu citirea datelor dintr-un
fiier cu numele INPUT1.TXT; altfel, se ncepe cu rezolvarea punctului (b)
presupunnd c[ datele de intrare se afl[ n fiierul INPUT2.TXT.
                      Ediia III (Varna - Bulgaria) octombrie 1995

            BOI.9. (Rezervoare). Un sistem de p[strare a a petrolului este format din
n(n200) rezervoare de volume date (maxim 100 unit[i de volum fiecare) i
n-1 conducte de volum neglijabil care leag[ rezervoarele dou[ cte dou[. 
Nu exist[ rezervoare izolate. Pentru umplerea lor se alege un rezervor s numit
surs[, n care se monteaz[ o pomp[. Sursa s r[mne permanent goal[ iar petrolul
este pompat prin fiecare din conductele t1,t2,.. .,tk conectate la s (o unitate
de volum prin fiecare conduct[ ntr-o unitate de timp) pn[ cnd toate rezervoarele,
nafar[ de surs[, sunt umplute. Deci procesul de umplere va necesita un timp egal
cu maximum dintre V1,V2,...,Vk, unde Vi,1ik este suma volumelor rezer-
voarelor umplute prin conducta ti.
Problem[:
Fiind dat sistemul de mai sus s[ se afle rezervorul surs[ optim astfel nct procesul
de umplere s[ se realizeze n cel mai scurt timp.
Intrare: Intrarea va fi dat[ ntr-un fiier ASCII de forma:
linia 1                                n- num[rul de rezervoare
linia i(2in+1)  v(i-1)                - volumul rezervorului i-1, num[r natural
linia i(n+2i2n) r q                               -  ntre rezervoarele r i q exist[ o
conduct[. Numerele r i q sunt separate printr-un singur spaiu.
Ieire: Ieirea va fi standard (ecran) i conine dou[ linii cu structura:
The number of optimal source is: ...
The optimal time is: ...


           BOI.10.(Numere mari). Un num[r natural n scris n baza zece avnd k
cifre, 25k80, se numete mare.
           S[ se scrie un program care, pentru un num[r mare n determin[ cel mai
mare ntreg p astfel nct p3+p2+3pn.
Intrare: Intrarea va fi un fiier ASCII n care pe prima linie se afl[ un num[r
ntreg k. Pe linia urm[toare se afl[ un num[r mare n cu k cifre zecimale.
Ieire: Ieirea va fi standard (ecran) i afieaz[ num[rul p.
Exemplu: Pentru intrarea:
46
1000000000000001000000000000003000000000000001
  programul va afia:
1000000000000000





                      BOI.11. (Clieni). O firm[ ocup[ zece etaje ale unei cl[diri, numerotate
de la 1 la 10. La terminarea lucrului, valetul John trebuie s[ transporte comisioane
ntre etaje. El pleac[ de la etajul 1 i revine la etajul 1. La un transport ntre etaje
(urcate sau coborte) duce un singur comision de la un client la altul, sau nu duce
nimic.
Problem[:
           Scriei un program care g[sete num[rul minim m de etaje urcate pentru a
deservi toi clienii (ordinea de deservire nu conteaz[).
Intrare: Comisioanele ntre clienii care trebuiesc deservii sunt date ntr-un fiier
text dup[ cum urmeaz[:
Pe prima linie: k (k50)  - num[rul comisioanelor;
Pe fiecare din urm[toarele k linii: dou[ numere care simbolizeaz[ etajul clientului
expeditor, respectiv etajul clientului destinatar ntre care are loc transportul
comisionului; de exemplu: 
7
1 10
3 2
4 3
6 7
8 9
3 4
4 3
Ieirea: Ieirea este standard (ecran) i conine num[rul m;
Pentru exemplul anterior ieirea este:
12
Observaie: John poate l[sa eventual un pachet la un etaj, pachet pe care s[-l ia mai
trziu.


           BOI.12. (Campionatul de fotbal). Una din sarcinile Ministerului Sportu-
rilor dintr-o ar[ balcanic[ este de a organiza un campionat de fotbal cu n echipe
(numerotate de la 1 la n). Campionatul const[ din n etape (dac[ n este impar) sau
n-1 etape (dac[ n este par); orice dou[ echipe disput[ ntre ele un joc i numai
unul.
Problem[: 
Scriei un program care realizeaz[ o programare a campionatului.
Intrare: Num[rul de echipe n (2n24) va fi dat la intrarea standard (consol[).
Ieire: Ieirea este standard (ecran) sub forma unui tabel cu numere ntregi avnd n
linii. Al j-lea element din linia i este num[rul echipei care joac[ cu echipa i n
etapa j (evident dac[ i joac[ cu k n etapa j, atunci n tabel k joac[ cu i n
aceeai etap[). Dac[ echipa i este liber[ n etapa j, atunci al j-lea element al
liniei i este zero.
Exemple:
           i) Dac[ datele de intrare sunt:
3
atunci ieirea trebuie s[ aib[ forma:
2 3 0
1 0 3
0 1 2
           ii) Pentru intrarea:
4
ieirea va fi:
2 3 4 
1 4 3
4 1 2
3 2 1


            BOI.13. (Rotaia cilindrilor). Un sistem conex de transmisie este format
din n(n30) cilindri, numerotai de la 1 la n. Dac[ cilindrii i i j sunt n contact
unul cu altul i unul din ei se nvrte ntr-un sens (Clockwise sau Opposite), atunci
cel[lalt se rotete n sens opus. Dac[ doi cilindri aflai n contact se rotesc n
aceeai direcie, atunci sistemul se blocheaz[ (vezi Figura 1).









                                      Figura 1
Problem[:
           S[ se scrie un program care, pentru un sistem de transmisie conex dat,
determin[ comportarea lui atunci cnd un cilindru precizat se nvrte ntr-un anumit
sens: se blocheaz[ sau lucreaz[ normal.
           Dac[ transmisia lucreaz[ normal, programul listeaz[ cilindrii i sensurile
lor de rotaie. In caz contrar, programul determin[ num[rul minim de cilindri
diferii de cilindrul i care trebuiesc eliminai din angrenajul blocat, astfel nct toi
cilindrii r[mai s[ se roteasc[ la rotirea cilindrului i.
Intrare: Intrarea este un fiier ASCII cu urm[torul format:
Prima linie conine num[rul n de cilindri i num[rul m de perechi de cilindri aflai
n contact;
Fiecare din urm[toarele m linii conine o pereche de cilindri n contact;
Ultima linie conine num[rul i al cilindrului care va fi rotit i un caracter (C sau
O) care simbolizeaz[ sensul s[u de rotire. Pentru transmisiile din Figura 1 intrarea
va fi:
5 5                       respectiv3 3 
1 2                                                                                1 2
1 3                                                                                1 3
2 4                                                                                2 3
3 4                                                                                1 O
3 5
1 C
Ieire: Ieirea va fi standard (ecran) i va consta din trei sau patru linii. Prima linie
descrie comportarea sistemului printr-o liter[: W (funcioneaz[) sau B (blocat).
Dac[ sistemul funcioneaz[, atunci a doua linie este o list[ a cilindrilor care se
rotesc Clockwise, iar a treia linie este o list[ a cilindrilor care se rotesc Opposite.
Dac[ sistemul este blocat, atunci a doua linie este o list[ a cilindrilor care se rotesc
Clockwise, a treia linie este o list[ a cilindrilor care se rotesc Opposite dup[ ce a
fost eliminat num[rul minim de cilindri, iar a patra linie conine cilindrii eliminai
(Removed) dup[ formatul de scriere de mai jos:
Pentru cele dou[ exemple anterioare ieirea va fi:
W                                          B
C 1 4 5                                    C 2
O 2 3                                      O 1
                                           R 3



                            Alte probleme propuse de juriu


            BOI.14. (Drumuri). S[ consider[m n plan n(1n100) puncte
cu coordonate numere ntregi.
a) S[ se afle un drum (linie poligonal[ deschis[) format din linii drepte, care trece
prin aceste puncte n aa fel nct num[rul de puncte de intersecie ale tuturor
acestor linii s[ fie minim.
b) S[ se afle un drum de lungime minim[ care s[ lege toate punctele;
c) S[ se afle dreptunghiul de arie minim[, avnd laturile paralele cu axele de
coordonate, care conine n interior sau pe laturi toate punctele date. S[ se mpart[
apoi acest dreptunghi ntr-un num[r minim de dreptunghiuri care au cele n puncte
numai pe laturi.
Intrare: Num[rul n i coordonatele vrfurilor (se dau la tastatur[)
Ieire: Mod grafic.
                                                               (Constana, 1993)
                      BOI.15. (GO). Consider[m o reea bidimensional[ mxn. Doi juc[tori
aeaz[ succesiv discuri n nodurile libere ale reelei (cte un disc la fiecare
moment); aceste aciuni le numim mic[ri. Primul juc[tor are numai discuri albe
(A), iar al doilea numai discuri roii (R).
           Primul juc[tor poate captura discuri roii dac[, punnd un disc alb ntr-un
nod liber, el nchide o zon[ a reelei acoperit[ cu discuri roii. O zon[ de discuri
roii este considerat[ nchis[ dac[ ea nu poate fi f[cut[ mai mare prin al[turarea
(pe orizontal[, vertical[ sau diagonal[) a unui nou disc rou lng[ alt disc  al
zonei.
           Considernd o poziie aleatoare a acestui joc, problema este de a determina
cea mai mare arie (arii) de discuri roii care poate fi nchis[ printr-o micare a
primului juc[tor.
Valorile lui m,n(m20,n80) sunt citite de la tastatur[.
Exemplu: Dac[ m=6,n=5 i poziia curent[ a jocului este:
           R      R       A                   A
            R      R                     AR
            A      A       A      A      A
            A      A       A      R      R
            R      A                     RR
            R      R       R      A      A
atunci ieirea va trebui s[ fie:
           R      R       A                   R
            R      R                     AR
            A      A       A      A      A
            A      A       A      C      C
            C      A                     CC
            C      C       C      A      A
                                                                          (idem)


           BOI.16. (Inflorescen[). Se d[ un alfabet construit cu caractere ASCII
(diferite de ' ') dintre care se desemneaz[ un caracter special numit mugure.
Acest mugure poate fi rescris sau ca o anumit[ secven[ de caractere din alfabet
sau ca orice alt caracter din alfabet. O secven[ f[r[ muguri obinut[ dintr-un
singur mugure dup[ aplicarea unui num[r nespecificat de reguli de rescriere se
numete floare.
           Se cere s[ se alc[tuiasc[ un program care, dup[ ce citete de la intrare o
secven[ de caractere ASCII, va decide dac[ ea este sau nu o floare.
           Structura datelor de intare se supune urm[toarelor reguli:
           a) Informaia despre alfabet se citete dintr-un fiier text al c[rui nume este
dat de la tastatur[; acest fiier are structura:

n
v1v2..vn
w
x1x2..xp
unde:
  - n(0<n<80) este un ntreg care reprezint[ num[rul de elemente ale alfabetului;
  - v1v2..vn sunt elementele alfabetului, scrise ca un ir de caractere ASCII;
  - w este un caracter ASCII care reprezint[ mugurele; el face parte din alfabet;
  - x1x2..xp este un ir de caractere care poate nlocui mugurele; sfritul acestui
ir este marcat cu ' '.
           Datele de ieire reprezint[ mesaje scrise pe ecran sub forma:
secventa s1s2..sk este o floare,   sau
secventa s1s2..sk nu este o floare
Exemplu: S[ presupunem c[ fiierul de intrare are urm[torul coninut:
6
abcxd+
x
x+x' '
           Dac[ secvena testat[ este de forma b+a+c' ' atunci r[spunsul va fi
secventa b+a+c este o floare
           Dac[ secvena testat[ este de forma c++d' ' atunci r[spunsul va fi:
secventa c++d nu este o floare
                                                                          (idem)


           BOI.17 (Imp[rire). Se consider[ o reea p[trat[ nxn (1n80) de
n2 puncte cu coordonate ntregi n plan. Plecnd dintr-un punct arbitrar situat pe
latura stng[, se traseaz[ o linie dreapt[ pn[ la punctul de pe latura din dreapta
aflat cu un rnd mai sus sau mai jos. Procedeul se repet[ cu acest punct, pn[ se
ajunge n final la un punct aflat pe prima sau pe ultima linie a reelei. Dou[ puncte
care au fost deja unite printr-o linie nu se mai pot lega printr-o a doua linie. Cnd
acest proces de trasare ia sfrit, toate punctele reelei se distribuie n trei p[ri:
A (punctele legate prin linii), B (punctele aflate deasupra celei mai sus linii) i C
(punctele situate sub cea mai de jos linie).
           S[ se scrie un program care s[ traseze toate liniile posibile astfel nct:
a) A i C s[ conin[ acelai num[r de puncte;
b) Punctele din B i C s[ formeze figuri plane congruente.
Intrare: n se citete de la tastatur[;
Ieire: mod grafic.
                                                                          (idem)



                      BOI.18. (Intersecie de corpuri). Intr-un spaiu n-dimensional (cazuri
posibile n=2,n=3) sunt date p(1p6) corpuri paralelipipedice P1,P2,..,Pp
avnd laturile paralele cu axele de coordonate (se admite i posibilitatea lungimii
zero pentru unele dimensiuni) i prin coordonatele unuia din vrfuri, anume acel vrf
ale c[rui coordonate au valori minime. Se consider[ numai coordonate numere
ntregi.
           a) S[ se scrie un program pentru care ieirea este intersecia tuturor acestor
corpuri, ntr-o form[ explicit[;
           b) Dac[ se mai d[ un alt paralelipiped P, s[ se scrie un program care s[
genereze comenzi pentru translat[rile corpurilor P1,P2,..,Pp n aa fel nct
intersecia lor n noua poziie s[ fie exact P.
                                                                          (idem)

           BOI.19. (Colorare). Fiind dat un set de segmente (intervale deschise) situ-
ate pe aceeai ax[, se cere colorarea lor cu un num[r minim de culori astfel nct
orice dou[ segmente care se intersecteaz[ s[ aib[ culori diferite.
           Fiecare interval este dat la intrare pe o linie sub forma unei perechi de
numere ntregi din intervalul [1,1000]; primul num[r este totdeauna mai mic
dect al doilea. Pe prima linie de intrare este precizat num[rul de segmente.
Exemplu: Pentru intrarea:
4
5 10
100 200
6 30
1 1000
ieirea va fi
3
                                                                  (Salonic 1994)


           BOI.20. (Tabel). Este problema BOI.8 n care (a) este schimbat cu:
(a') Se nlocuiete fiecare num[r x (1x100) cu num[rul y=f(x) unde y este
num[rul de zerouri cu care se termin[ x!. De exemplu:
x=8                       f(8)=1
x=15                       f(15)=3
x=53                       f(53)=12
                                                                          (idem)




                      BOI.21. (Interviu). Compania XYZ caut[ s[ angajeze personal pentru cele
n posturi vacante pe care le are. La ofert[ r[spund exact n persoane. Comitetul de
selecie ar avea o misiune simpl[ dac[ fiecare din solicitani i-ar fi precizat postul
pe care dorete s[-l ocupe. Dar, datorit[ unor conjuncturi financiare nefavorabile
i a unei rate de omaj crescute, toate persoanele i declar[ disponibilitatea de
ocupa orice post. Deci comitetul va trebui s[ rezolve problema de a g[si persoana
cea mai indicat[ pentru fiecare post.
Considerai c[ suntei membru al acestui comitet i vi se cere o cea mai bun[
soluie. Regula dup[ care facei asignarea fiec[rei persoane la un post va trebui s[
in[ cont de condiiile cerute de postul respectiv (studii, experien[, recomand[ri,
abilit[i psihice, etc.). Aa c[ vei fi nevoii ca - n prima faz[ - s[ chemai la
interviu pe fiecare candidat pentru a-i aprecia (folosind un anumit punctaj) capaci-
tatea sa de a ocupa un anumit post. Dup[ ce ai strns toate datele necesare (i v-ai
f[cut o impresie) despre fiecare candidat, facei o ordonare descresc[toare a
candidailor care ar putea ocupa acest post. Bineneles, ideal ar fi ca fiecare
candidat s[ ocupe postul pe care i l-ar dori; aceasta este imposibil dac[ pentru
postul respectiv candideaz[ altul care s-a dovedit mai bun. Nu uitai c[ avei o
funcie foarte nalt[ la XYZ i suntei pl[tit cu 200.000 dolari pe an, aa c[ nu
putei fi mituit. Se consider[ de aceea c[ avei interes s[ v[ protejai compania i
vei prezenta cea mai bun[ soluie de angajare din punctul ei de vedere. Propunerile
dvs. vor fi f[cute n ordine strict descresc[toare a punctajului total pe care l-ai
stabilit pentru fiecare candidat.
Exemplu: Datele de intrare sunt referitoare la capacitatea fiec[rui candidat de a
ocupa un anumit post; ele sunt date ntr-o tabel[ cu n(1n10) linii (reprezentnd
posturile) i n coloane (candidaii). Pe prima linie se afl[ un singur num[r - n, iar
pe fiecare din urm[toarele n linii sunt date recomand[rile referitoare la capacitatea
fiec[rui candidat de a ocupa postul, codificate n numere ntregi din [0,20],
separate prin cel puin un spaiu. De exemplu:
4
4  6 14 11
7  2  8  9
3 13  1  4
5  2  0 13
La ieire, poziia ocupat[ de fiecare candidat este dat[ pe cte o linie num[rat[
separat. Referitor la exemplul anterior, r[spunsul este:
1  1
2  2
3  4
4  3
                                                                           (idem)


                      BOI.22. (Servire). Un sistem de operare numit server trebuie s[
"serveasc[" mai muli clieni clasificai n k(1k20) grupuri. Fiecare astfel de
grup este identificat printr-un num[r ntreg pozitiv. Clienii fiec[rui grup au
asigurat[ cte o prioritate - un num[r pozitiv p(0p65000). Cu ct este mai
mic num[rul, cu att este mai mare prioritatea n interiorul grupului.
           Serverul lucreaz[ n pai. La fiecare pas 0,1 sau mai muli clieni solicit[
un serviciu. La un pas poate fi ndeplinit un singur serviciu (dac[ exist[ cerere);
toate celelalte cereri trebuie s[ atepte paii urm[tori.
           Servirea grupurilor este secvenial[ (n ordinea apariiei primului client din
grup) i ciclic[ (dup[ ce s-a servit un client din fiecare grup, serverul se ntoarce
la primul grup servit .a.m.d.). Dac[ ntre timp apare primul client al unui nou grup,
el este servit imediat i grupul lui este inserat la locul lui n ciclul grupurilor,
conform regulilor de servire.
           Clienii unui grup sunt servii conform priorit[ii. Dac[ ntr-un grup apar
mai muli clieni cu prioritate egal[, primul venit este servit nti. Dac[ vin
simultan mai muli clieni cu prioritate egal[ din acelai grup, alegerea serverului
este arbitrar[.
Problem[:
           Se cere un program care s[ realizeze procesul de servire pas cu pas. La
fiecare pas, el trebuie s[:
 i) citeasc[ de la tastatur[ lista clienilor care cer serviciu la acest pas (lista vid[
dac[ nu exist[ clieni);
 ii) scrie pe ecran identificatorul clientului servit la acest pas.
Intrare: Lista clienilor se scrie pe o linie la intrare. Dac[ vin n clieni, linia const[
din 2n+1 numere ntregi separate printr-un spaiu: nti num[rul n, apoi 2n numere
grupate n perechi num[r-grup prioritate pentru fiecare client. Lista vid[
const[ din cifra 0 la nceputul liniei. Dac[ primul num[r de pe linie este -1, datele
de intrare s-au terminat. De exemplu:
4 15 7 2 1 15 2 2 10
0
0
0
0
1 2 1
-1
Ieire: La fiecare pas programul scrie pe o linie de ecran num[rul grupului i
prioritatea clientului servit la acest pas, precum i num[rul pasului n care clientul
a intrat n sistem. Dac[ nu sunt clieni de servit, se scrie pe ecran cifra 0. Pentru
intrarea din exemplul anterior, ieirea va fi:
15 2 1
2 1 1
15 7 1
2 10 1
2 1 5
                                                                   (Varna, 1995)


           B.23. (Siluete). Figura determinat[ de o secven[ de coordonate numere
ntregi (x1,0),(x1,y1),(x2,y1),..(xk-1,yk-1),(xk,yk-1),(xk,0) astfel
nct x1<x2<..<xk, se numete poli-linie sau cladire (vezi figura). Consider[m o
colecie de n poli-linii (cl[diri) numerotate cu numerele 1,2,..,n. Cl[direa cu
num[rul i este n spatele cl[dirii cu num[rul j dac[ i<j; astfel, prima cl[dire
este n spatele tuturor cl[dirilor, iar cl[direa n este n faa tuturor. Cnd o cl[dire
i este n spatele cl[dirii j, partea comun[ a celor dou[ cl[diri care aparine primei
cl[diri nu este vizibil[. Poli-linia (sau poli-liniile) care m[rginete ntreaga colecie
de cl[diri este numit[ siluet[ a coleciei.
Problem[:
           Scriei un program care, pentru o colecie dat[ de poli-linii, realizeaz[
urm[toarele:
   - determin[ silueta coleciei;
   - afl[ numerele cl[dirilor vizibile (cl[direa este considerat[ vizibil[ dac[ o parte
a ei este vizibil[);
   - determin[ aria celei mai mari p[ri vizibile dintr-o cl[dire.



                                                                                        (x2,y2)(x3,y2)


                                                                                            (x2,y1)
                               (x1,y1)



                               (x1,0)                (x3,0)


                                                                                        Figura 2

Intrare: Datele de intrare sunt ntr-un fiier ASCII. Prima linie conine un singur
num[r ntreg n - num[rul cl[dirilor din colecie. Urm[toarele n linii conin
coordonatele primei, a doua,.., a n-a poli-linii. Dac[ o poli-linie este determinat[
de 2k puncte, linia ei va consta din numerele ntregi x1,y1,x2, y2,..,yk-1,xk
separate prin cte un spaiu.
Ieire: Ieirea va fi standard. Pe prima linie programul va scoate un singur num[r
ntreg m - num[rul de poli-linii diferite reprezentnd silueta cl[dirilor. Fiecare din
urm[toarele m linii conine coordonatele unei poli-linii din siluet[ (conform
formatului de intrare). Pe urm[toarea linie programul va scrie num[rul de cl[diri
vizibile (numere ntregi separate prin cte un spaiu). Ultima linie va avea un singur
num[r ntreg: suprafaa celei mai mari arii vizibile dintr-o cl[dire.
Exemple:
Intrare                                                                                         Ieire
3                                                                                                                           1
0 10 6 16 10                                         0 10 6 16 10 14 17
8 6 14                                                                1 3
7 14 17                                                                                         140

4                                                                                                                           2
5 10 9 6 15                                            5 10 9 6 13 12 16
13 12 16                                                                                     19 7 8 20 23
20 8 23                                                                                         1 2 3 4
19 7 21                                                                                         64


           BOI.24. (Numere pe tabl[). Fie A o tabel[ cu m linii i n coloane
(2m8,1n8). Fiecare celul[ din tabel[ este colorat[ n alb sau negru i
conine o cifr[ zecimal[. Fie B o tabel[ cu m linii construit[ prin alipirea unui
num[r arbitrar de copii ale tabelei A. Figura arat[ un exemplu pentru cazul m=6,
n=5 (a n+1-a coloan[ a lui B este egal[ cu prima coloan[ a lui A, etc.).

            1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16....
            1  7  2  1  5  2  7  2  1  5  2  7  2  1  5  2
            2  4  3  6  0  8  4  3  6  0  8  4  3  6  0  8
            3  7  2  2  6  0  7  2  2  6  0  7  2  2  6  0
            4  6  9  4  1  5  6  9  4  1  5  6  9  4  1  5
            5  6  7  0  2  5  6  7  0  2  5  6  7  0  2  5
            6  7  4  7  3  1  7  4  7  3  1  7  4  7  3  1

                                      Figura 3

           Dou[ celule ale tabelei B sunt vecine dac[ au aceeai culoare i o latur[
comun[. Un num[r X este n tabel[ dac[ cifrele sale sunt luate secvenial (stnga
dreapta) din celule diferite ale tabelei B; prima celul[ este pe prima coloan[ a lui
B, iar fiecare celul[ care urmeaz[ este deasupra, dedesubt sau la dreapta celei
precedente. Numerele de pe tabl[ sunt negre sau albe, dup[ culoarea celulelor
corespunz[toare. De exemplu, 7,72,723,7236 sunt numere albe din tabela de
sus. Num[rul X este o parte al num[rului Y dac[ X poate fi obinut din Y tergnd
0,1 sau mai multe cifre. de exemplu, 273 este o parte a lui 7320250723 dar nu
i o parte a lui 730250722. Distana dintre dou[ numere X i Y de k cifre fiecare
este dat[ de relaia i|xi-yi| unde xi,yi (1ik) sunt cifrele lui X respectiv
Y.
Problem[:
           Trebuie s[ scriei un program care, pentru o tabel[ A i un num[r k:
   - g[sete cel mai mare num[r alb de k cifre din tabela B;
   - g[sete cel mai mic num[r negru de k cifre din tabela B;
   - g[sete cel mai mare num[r care este n acelai timp o parte a num[rului
maximal alb de k cifre i a num[rului minimal negru de k cifre din tabela B;
   - g[sete dou[ numere din tabela B de k cifre i culori diferite, care au distana
minim[ ntre ele.
Intrare: Datele de intrare pentru toate testele sunt ntr-un fiier ASCII. Datele pentru
fiecare test sunt de forma:
a) pe prima linie: m,n,k separate prin cel puin cte un spaiu;
b) urm[toarele m linii: tabela A. Pentru fiecare celul[ se d[ o secven[ de dou[
caractere f[r[ nici un spaiu ntre ele: o cifr[ zecimal[ i o liter[ ('b' pentru
celulele negre i 'w' pentru cele albe). Perechile pentru o linie a tabelei sunt date
de la stnga la dreapta i sunt separate prin cel puin un spaiu.
Ieire: Rezultatele programului vor fi scrise ntr-un fiier ASCII. Pentru fiecare set
de date de intrare, ieirea va avea forma:
TEST: <numar>
MAX WHITE NUMBER: <numar tabela>
MIN BLACK NUMBER: <numar tabela>
MAX NUMBER "PART OF": <number>
CLOSEST PAIR OF NUMBERS: <primul numar din tabela>
                   <al doilea numar din tabela>



                      Soluii ale problemelor date la Balcaniad[

            BOI 1 (Adrian Atanasiu):  
           Rezolvarea problemei se bazeaz[ pe urm[toarele idei:
  - n culoare se determin[ un obiect necolorat (primul element notat cu 1);
  - se pune pe acest element o culoare nou[;
  - se trimite la pata, care coloreaz[ cu aceeai culoare tot obiectul; pentru a scrie
mai uor algoritmul, tabloul a a fost bordat cu cte o linie i o coloan[ suplimentare
umplute cu 0;
  - procedeul se repet[ pn[ nu se mai g[sesc obiecte necolorate (toate elementele
tabloului sunt diferite de 1).
Se trece apoi la rezolvarea punctului (a) folosind procedura dreptunghi, anume:
   - se g[sete culoarea care predomin[ n tablou; ea aparne obiectului de m[rime
maxim[ i este reinut[ n variabila fond;
  - se determin[ punctele cu aceast[ culoare care au coordonate extreme: cei mai
mici si cei mai mari x i y; prin aceste puncte vor trece laturile dreptunghiului.
Observaie: S-a presupus c[ este vorba de un dreptunghi cu laturile paralele cu
axele de coordonate.
   Pentru rezolvarea punctului (b) se folosete procedura plasare; ea aduce prin
intermediul tabloului model, copii ale obiectului maximal n toate poziiile i veri-
fic[ dac[ ele pot fi aezate n tablou f[r[ a se suprapune cu altele.
   Procedura mutare asigur[ diverse poziii ale obiectului.
In final se p[streaz[ tabloul n care au putut fi introduse un num[r maxim de copii.
program obiecte;
uses crt;
var
 a:array[0..20,0..20] of integer; {a se bordeaza cu elemente 0}
  b,model:array[1..19,1..19] of integer;
  m,n,i,j,culoare,fond:integer;
  minx,miny,maxx,maxy,x1,y1:integer;
  s:boolean;
------------------------------------------------
procedure pata;
{marcheaza cu culoare tot obiectul insemnat}
var
  ii,jj,k1,k2:integer;
  vecin:boolean;
begin
  repeat
  vecin:=false;
  for ii:=1 to m do
    for jj:=1 to n do
      if a[ii,jj]=culoare then
         for k1:=ii-1 to ii+1 do
            for k2:=jj-1 to jj+1 do
              if a[k1,k2]=1 then begin
a[k1,k2]:=culoare;vecin:=true end
  until vecin=false
end;
--------------------------------------------------
procedure marcaj;
{se delimiteaza obiectele, marcand fiecare obiect printr-un
numar supraunitar}
begin
   culoare:=1;
   for i:=1 to m do
     for j:=1 to n do
        if a[i,j]=1 then begin
          culoare:=culoare+1; a[i,j]:=culoare;
          pata end
end;
------------------------------------------------------
procedure dreptunghi;
{se determina cel mai mare obiect si se incadreaza intr-un
dreptunghi}
var
  max,obj,r,s:integer;
begin
  max:=0; fond:=0;
  for i:=2 to culoare do begin
    obj:=0;
    for r:=1 to m do
      for s:=1 to n do
         if a[r,s]=i then obj:=obj+1;
    if max<obj then begin max:=obj;fond:=i end
                        end;
  {obiectul maxim are culoarea i retinuta din fond}
  {se determina acum coordonatele extreme ale obiectului
maximal}
  minx:=m;miny:=n;maxx:=1;maxy:=1;
  for r:=1 to m do
     for s:=1 to n do
       if a[r,s]=fond then begin
           if minx>r then minx:=r;
           if maxx<r then maxx:=r;
           if miny>s then miny:=s;
           if maxy<s then maxy:=s end;
  writeln('Obiectul maximal este cuprins in dreptunghiul de
varfuri:');
  writeln('(',minx,',',miny,')  (',maxx,',',miny,') 
(',maxx,',',maxy,')  (',minx,',',maxy,')');
end;
-------------------------------------------------------
procedure mutare;
var
  im,ii,wx,wy,jm,jj:integer;
begin
  im:=1;jm:=0;s:=true;
  wx:=m-maxx+minx;wy:=n-maxy+miny;
    repeat
    jm:=jm+1;
    if jm>wy then begin im:=im+1; jm:=1 end;
  until b[im,jm]=1;
  for ii:=1 to m do
    for jj:=1 to n do b[ii,jj]:=0;
{deplasarea obiectului in b. Daca a fost posibila deplasarea
s:=false; daca deplasarea nu a fost posibila, s:=true si
obiectul se rearanjeaza la pozitia initiala, cu coltul din
stanga sus pe (x1,y1+1) sau (x1+1,y1)}
  if (im=wx) and (jm=wy) then begin
     for ii:=1 to maxx-minx+1 do
       for jj:=1 to maxy-miny+1 do
         if y1<wy then b[x1+ii-1,y1+jj]:=model[ii,jj]
     else if x1<wx then  b[x1+ii,y1+jj-1]:=model[ii,jj] end
         else begin
       for ii:=1 to maxx-minx+1 do
         for jj:=1 to maxy-miny+1 do
             if jm<wy then begin 
                           s:=false; b[im+ii-1,jm+jj]:=model[ii,jj] end
                      else b[x1+ii,y1+jj-1]:=model[ii,jj]
                      end
end;
---------------------------------------------------------------
procedure plasare;
var
  c,final:array[1..19,1..19] of integer;
  suprapus:boolean;
  p,maxobj:integer;
begin
  for i:=1 to m do
     for j:=1 to n do begin
        if a[i,j]=fond then b[i-minx+1,j-miny+1]:=1
                       else b[i-minx+1,j-miny+1]:=0;
        if a[i,j]>0 then a[i,j]:=1;
                     end;
  for i:=0 to maxx-minx do
    for j:=0 to maxy-miny do model[i+1,j+1]:=b[i+1,j+1];
  maxobj:=0;
  for x1:=1 to m-maxx+minx do
    for y1:=1 to n-maxy+miny do begin
      p:=0;
      for i:=1 to m do
        for j:=1 to n do c[i,j]:=a[i,j];
  repeat
    suprapus:=false;
    for i:=1 to m do
       for j:=1 to n do begin
          c[i,j]:=c[i,j]+b[i,j];
          if c[i,j]=2 then suprapus:=true end;
    if suprapus then
       for i:=1 to m do
          for j:=1 to n do c[i,j]:=c[i,j]-b[i,j]
                else p:=p+1;
    mutare
    until s;
  if maxobj<p then begin
     maxobj:=p;
     for i:=1 to m do
        for j:=1 to n do final[i,j]:=c[i,j]
                   end;
                         end;
  writeln('Noua configuratie contine ',maxobj, ' copii ale
obiectului maximal:');
  for i:=1 to m do begin
     for j:=1 to n do write(final[i,j],' ');
     writeln end;
end;
----------------------------------------------------------------
begin {program principal}
  clrscr;
  write('dati dimensiunile tabloului: ');readln(m,n);
  writeln('dati elementele tabloului:');
  for i:=0 to 20 do
     for j:=0 to 20 do a[i,j]:=0;
  for i:=1 to m do begin
    for j:=1 to n do read(a[i,j]);
    readln end;
  marcaj;
    writeln('Obiectele marcate sunt:');
  for i:=1 to m do begin
    for j:=1 to n do write(a[i,j],'  ');
    writeln end;
  dreptunghi;
  plasare
end.

          BOI 2 (Vlad Atanasiu):
           Programul a fost construit folosind comentarii care l fac uor de neles.
program go;
uses crt;
type varianta = record
                culori:array[1..5] of byte;
                negre,albe:byte;
                end;
     raspunsuri = record
                  numar:byte;
                  variante:array[1..10] of varianta;
                  end;
var v_:varianta;
    r_:raspunsuri;
    i:integer;
---------------------------------------------------------
procedure next(var v_:varianta); 
{ intoarce in v_ urmatoarea combinatie posibila. Avansarea se
face prin numararea in baza 6 cu cifrele 1-6 in loc de 0-5. In
momentul cand a 5-a cifra s-a modificat, inseamna ca toate
variantele pe 4 cifre au fost acoperite (1111-6666) }
var i:integer;
begin
   inc(v_.culori[1]);
   for i:=1 to 4 do
     if v_.culori[i]>6 then
        begin
          v_.culori[i]:=1; inc(v_.culori[i+1]);
        end;
  if v_.culori[5]=2 then
     begin
       writeln('EROARE !!! '); halt(1);
{ daca s-a ajuns la ultima varianta posibila fara sa se
   gaseasca o solutie semnaleaza eroare }
     end;
end;
------------------------------------------------------------
function acopera(v1,v2:varianta):boolean;
{ v1 este varianta care trebuie incercata, v2 este varianta care
se testeaza daca indeplineste conditiile cu v1 ca solutie }
var i,j,negre,albe:byte;
begin
   negre:=0; albe:=0;
   for i:=1 to 4 do 
    if v1.culori[i]=v2.culori[i] then
     begin inc(negre); v2.culori[i]:=0; v1.culori[i]:=0; end;
   if negre=v2.negre then
      for i:=1 to 4 do
        for j:=1 to 4 do
          if (v2.culori[j]=v1.culori[i]) and
              (v2.culori[j]<>0) then
             begin
          inc(albe); v2.culori[j]:=0; v1.culori[i]:=0;
             end;
   acopera:=(negre=v2.negre) and (albe=v2.albe);
{ intoarce True daca varianta curenta este acoperita de cele
analizate anterior. }
end;
---------------------------------------------------------
procedure ask_and_add(v1:varianta);
{ afiseaza varianta v1 (prima varianta gasita care indeplineste
conditiile puse de raspunsurile la variantele anterioare) si
intreaba datele despre ea }
var i:integer;
begin
   inc(r_.numar); r_.variante[r_.numar]:=v1;
   write('varianta mea : ');
   for i:=1 to 4 do write(v1.culori[i],' ');
   write('a) '); readln(r_.variante[r_.numar].negre);
   gotoxy(37,wherey-1);
   write('b) '); read(r_.variante[r_.numar].albe);
end;
---------------------------------------------------------
function merge(v_:varianta):boolean;
{ intoarce True daca varianta curenta ar trebui sa fie intrebata
ca urmatoare solutie }
var i,j:integer;
    m:boolean;
begin
   m:=true; i:=1;
   while (i<=r_.numar) and m do
---------------------------------------------------------
      begin
        m:=acopera(v_,r_.variante[i]); inc(i);
      end;
   merge:=m;
end;
---------------------------------------------------------
begin {Program principal }
   clrscr; r_.numar:=0;
   for i:=1 to 5 do v_.culori[i]:=1; 
{initializeaza prima varianta posibila la 1111 }
   writeln('Alegeti o secventa de 4 cifre');
   while (r_.variante[r_.numar].negre<>4)or(r_.numar=0) do
      begin
        while not(merge(v_)) do next(v_); 
{trece la urmatoarea varianta posibila pana cand gaseste una
care ar trebui intrebata ca urmatoare solutie }
        ask_and_add(v_); {si o intreaba }
      end;
end.

          BOI 3 (Adrian Atanasiu):
           Se genereaz[ toate puterile lui 2 pn[ la n; ele vor intra n irul aditiv.
In faza a doua, toate puterile lui 2 care apar efectiv n scrierea lui n sunt colectate
separat n vectorul aux; sumele lor dou[ cte dou[ ncepnd cu cele mai mici sunt
introduse n ir. Ceea ce se obine n final se ordoneaz[ cresc[tor.
           Dac[ n este o putere a lui 2, el va apare n ir din faza de generare a
puterilor lui 2; altfel, va fi obinut ca ultima sum[ din aux;
Atenie ! Algoritmul nu este bun pentru numerele de forma n=2k-1, pentru care se
obine un ir mai lung cu un termen dect unul minim.
           In acest caz s-a folosit urm[toarea idee - valabil[ pentru n>7, n=2k-1:
- primele k-1 elemente din a sunt a[1]=20,a[2]=21,..,a[k-1]=2k-2;
- urmeaz[ dou[ elemente calculate deosebit: 
                             a[k]=a[k-1]+1; a[k+1]=2*a[k];
- fiecare element care urmeaz[ este calculat adunnd la precedentul num[rul care
urmeaz[ din secvena a[3],a[4],..,a[k-2];
- num[rul final 2k-1 se obine adunnd ultimul num[r din secven[ cu a[k].
   Este interesant de demonstrat matematic valabilitatea acestui algoritm.
program aditiv;
uses crt;
var
 a,aux,bin:array[1..20] of integer;
 n,m,term,i,j,k:integer;
-------------------------------------------------------------
procedure binar;
var
 p:integer;
begin
  term:=0; p:=n;
  while p>0 do begin
     term:=term+1; bin[term]:=p mod 2; p:=p div 2 end;
end;
-------------------------------------------------------
procedure ordonare;
var
   x:integer;
   schimba:boolean;
begin
   if term<m then
      repeat
       schimba:=true;
       for i:=1 to m-1 do
          if a[i]>a[i+1] then begin
             x:=a[i];a[i]:=a[i+1];a[i+1]:=x;schimba:=false end
      until schimba;
end;
------------------------------------------------------------
begin  {Program principal}
  clrscr;
  write('Dati numarul final n='); readln(n);
  binar;
  a[1]:=1;m:=term;
  if bin[1]=1 then begin j:=1; aux[1]:=1 end
                   else j:=0;
  for i:=2 to term do begin
     a[i]:=2*a[i-1];
     if bin[i]=1 then begin
        j:=j+1; aux[j]:=a[i] end end;
  if (j>1) and (j<term) then
        for i:=2 to j do begin
           aux[i]:=aux[i-1]+aux[i];
           m:=m+1; a[m]:=aux[i] end
                        else
            if (j=term) and (m>3) then begin
                a[m]:=a[m-1]+1;
                a[m+1]:=2*a[m];m:=m+2; i:=3;
                while i<=term-2 do begin
                    a[m]:=a[m-1]+a[i];i:=i+1;m:=m+1 end;
                a[m]:=a[m-1]+a[term] end
                            else
                if m=2 then begin m:=m+1;a[m]:=3 end
                       else if m=3 then begin
                           m:=m+2;a[m-1]:=3;a[m]:=7 end;
  ordonare;
  writeln('Sirul aditiv obtinut are ',m,' termeni:');
  for i:=1 to m do write(a[i],' ');
end.

          BOI 4 (Vlad Atanasiu):
uses crt;
type pers_l=^persoana;
     persoana=record
                    cod:integer;
                    urm:pers_l;
              end;
     masa_l=^masa;
     masa=record
                lista:pers_l;
                urm:masa_l;
                nr_pers:integer;
          end;
     pereche_l=^pereche;
     pereche=record
             cod1,cod2:integer;
             urm:pereche_l;
             end;
var start,curent:masa_l;
  p_start,p_curent,c_start,c_curent,p_pastreaza:pereche_l;
{ Vor exista doua liste de perechi. A doua lista (c) va folosi
la pastrarea legaturilor care se taie pentru a evita formarea
ciclurilor. Inainte de punctul d) aceasta lista se adauga la
cealalta deoarece va fi necesara cunosterea tuturor legaturilor
pentru rezolvarea acelui punct }
    ciclu,necunoscuti:boolean;
    a,b,min_timp,nr_mese,maxim:integer;
---------------------------------------------------------
function cauta(cod:integer;m:masa_l):boolean;
{intoarce True daca persoana cod se afla la masa m}
var gasit:boolean;
    p:pers_l;
begin
   gasit:=false;
   p:=m^.lista;
   while (p<>nil) and not gasit do
      begin
        if p^.cod=cod then gasit:=true;
        p:=p^.urm;
      end;
   cauta:=gasit;
end;
---------------------------------------------------------
procedure insereaza_unul(var m:masa_l;cod:integer);
{ insereaza persoana cod la masa m }
var p:pers_l;
begin
   p:=m^.lista; new(m^.lista); 
   m^.lista^.cod:=cod; m^.lista^.urm:=p;
   inc(m^.nr_pers);
end;
---------------------------------------------------------
procedure concat(var m1,m2:masa_l);
{ concateneaza mesele m1 si m2 si sterge masa m2 }
var p:pers_l;
    m:masa_l;
begin
   p:=m1^.lista;
   while p^.urm<>nil do p:=p^.urm;
   p^.urm:=m2^.lista;m1^.nr_pers:=m1^.nr_pers+m2^.nr_pers;
   m:=start;
   if m<>m2 then begin
       while m^.urm<>m2 do m:=m^.urm;
       m^.urm:=m2^.urm;
                 end
            else start:=m2^.urm;
   dispose(m2);
end;
---------------------------------------------------------
procedure insereaza(cod1,cod2:integer;unul:boolean);
{ insereaza una sau doua persoane la mese }
var p:pers_l;
    masa1,masa2:masa_l;
begin
   if unul then
{daca este doar o persoana, se creeaza o masa pentru ea}
     begin
       curent:=start; new(start);
       start^.nr_pers:=0; start^.lista:=nil;
       insereaza_unul(start,cod1); 
{persoana este pusa la acea masa}
       start^.urm:=curent;
     end
           else begin
       curent:=start;
       masa1:=nil; 
{masa la care va fi gasita persoana cu codul 1 }
       masa2:=nil; 
{ masa la care va fi gasita persoana cu codul 2 }
       while curent<>nil do begin
           if cauta(cod1,curent) then masa1:=curent;
           if cauta(cod2,curent) then masa2:=curent;
           curent:=curent^.urm;
         end;
      if (masa1<>nil) and (masa2=nil) then 
{ daca primul are masa si al doilea nu }
        insereaza_unul(masa1,cod2) 
{ este pus si al doilea la masa primului }
                                     else 
      if (masa1=nil) and (masa2<>nil) then 
{ daca invers }
        insereaza_unul(masa2,cod1) 
{ este pus primul la masa celuilalt}
                                      else 
         if (masa1=nil) and (masa2=nil) then 
{ daca nici unul nu e la vreo masa }
            begin
              curent:=start; { se creeaza o masa noua }
              new(start);
              start^.nr_pers:=0; start^.lista:=nil;
              insereaza_unul(start,cod1); 
{ si sunt puse la acea masa ambele persoane }
     insereaza_unul(start,cod2); start^.urm:=curent;
            end
                                        else 
{ daca amandoi se afla la cate o masa }
           if masa1<>masa2 then 
{ se actioneaza doar daca sunt la mese diferite }
              concat(masa1,masa2) 
{ se concateneaza mesele intr-una singura }
                           else
                begin
                   ciclu:=true; 
{ daca ambele persoane exista la aceeasi masa, se semnaleaza ca
exista ciclu si legatura este pusa la lista de legaturi care
formeaza ciclu}
                c_curent:=c_start; new(c_start);
                c_start^.cod1:=cod1; c_start^.cod 2:=cod2;
                c_start^.urm:=c_curent;
                end;
             end;
end;
---------------------------------------------------------
procedure afiseaza_masa(m:masa_l);
{ afiseaza persoanele de la masa m }
var p:pers_l;
begin
   p:=m^.lista; write(m^.nr_pers,' persoane : ');
   while p<>nil do begin
        write(p^.cod,' '); p:=p^.urm;
                   end;
end;
---------------------------------------------------------
procedure citeste;
{ citeste datele din fisierul de intrare. Persoanele le adauga
la mese, si unple listele de legaturi p si c (legaturile care
se taie pentru a nu forma cicluri }
var t:text;
    cod1,cod2:integer;
    unul:boolean;
begin
   assign(t,'input49'); reset(t);
   while not eof(t) do begin
        ciclu:=false; unul:=true; read(t,cod1);
        if cod1>maxim then maxim:=cod1;
        p_curent:=p_start;
        if not eoln(t) then begin
             read(t,cod2);
             if cod2>maxim then maxim:=cod2;
             unul:=false;
                            end;
       insereaza(cod1,cod2,unul);
       if not ciclu then 
{daca legatura nu formeaza ciclu este pusa la lista p }
          begin
            new(p_start);
            p_start^.cod1:=cod1; p_start^.cod2:=0;
            p_start^.urm:=p_curent;
            if not unul then p_start^.cod2:=cod2;
         end;
                      end;
end;
---------------------------------------------------------
function max(i,j:integer):integer;
{ intoarce maximul a doi intregi }
begin
   if i>=j then max:=i else max:=j;
end;
---------------------------------------------------------
function lungime(cod,codn:integer):integer;
{ functie recursiva pentru aflarea timpului de comunicare al
persoanei cod. Se foloseste algoritmul clasic de aflare a
adancimii unui arbore. Variabila cond este folosita pentru a nu
se intra intr-o ciclare infinita pe aceeasi legatura.}
var lung:integer;
    pc:pereche_l;
begin
   lung:=0; pc:=p_start;
   while pc<>nil do
      begin
        if pc^.cod2<>0 then
          if (pc^.cod2=cod) and (pc^.cod1<>codn) then
            lung:=max(lung,lungime(pc^.cod1,cod)+1)
                                                 else 
            if (pc^.cod1=cod) and (pc^.cod2<>codn) then
              lung:=max(lung,lungime(pc^.cod2,cod)+1);
        pc:=pc^.urm;
      end;
   lungime:=lung;
end;
---------------------------------------------------------
function lider(m:masa_l):integer;
{ intoarce liderul mesei m, iar variabila globala min_timp va
fi actualizata la valoarea timpului de comunicare al celorlalte
persoane cu acesta }
var p:pers_l;
    x:integer;
begin
   min_timp:=500; p:=m^.lista; lider:=0;
   while p<>nil do 
{ se cauta persoana cu cel mai mic timp de comunicare de la masa
respectiva }
      begin
        x:=lungime(p^.cod,0);
        if x<min_timp then begin
            min_timp:=x; lider:=p^.cod;
                           end;
        p:=p^.urm;
      end;
end;
---------------------------------------------------------------
procedure insert_pereche
(cod,cod_prieten_1,cod_prieten_2:integer);
{insereaza legaturile cod-cod_prieten_1 si cod-cod_prieten_2 (
pentru legarea meselor) in lista p. Este exclus oricum ca aceste
legaturi sa produca cicluri.}
begin
   p_curent:=p_start; new(p_start);
   p_start^.cod1:=cod; p_start^.cod2:=cod_prieten_1; 
   new(p_start^.urm);
   p_start^.urm^.cod1:=cod;
   p_start^.urm^.cod2:=cod_prieten_2;
   p_start^.urm^.urm:=p_curent;
end;
---------------------------------------------------------
procedure ordoneaza;
{ ordoneaza mesele dupa numarul de persoane de la fiecare.
Unirea lor se va face optim in aceasta ordine. }
var m:masa_l;
    n:pers_l;
    i,j:integer;
begin
   for i:=1 to nr_mese do
      begin
         m:=start;
         while m^.urm<>nil do
            begin
              if m^.nr_pers>m^.urm^.nr_pers then
                 begin
                   n:=m^.lista; m^.lista:=m^.urm^.lista;
                   m^.urm^.lista:=n; j:=m^.nr_pers;
                   m^.nr_pers:=m^.urm^.nr_pers;
                   m^.urm^.nr_pers:=j;
                end;
             m:=m^.urm;
           end;
      end;
end;
---------------------------------------------------------
function cunoscuti(cod:integer):integer;
{ intoarce numarul de cunoscuti ai unei persoane }
var x:integer;
begin
   x:=0;
   p_curent:=p_start; { ii cauta in lista de legaturi }
   while p_curent<>nil do
      begin
      if (p_curent^.cod2<>0) and ((p_curent^.cod1=cod) or
           (p_curent^.cod2=cod)) then inc(x);
        p_curent:=p_curent^.urm;
      end;
   cunoscuti:=x;
end;
---------------------------------------------------------
function boss(m:masa_l):integer;
{determina persoana cu cei mai multi cunoscuti de la masa}
var p:pers_l;
    b,x,maxim_cunoscuti:integer;
begin
   p:=m^.lista; b:=0; maxim_cunoscuti:=0;
   while p<>nil do
      begin
        x:=cunoscuti(p^.cod);
        if maxim_cunoscuti<x then
           begin
             b:=p^.cod; maxim_cunoscuti:=x;
          end;
        p:=p^.urm;
      end;
   if maxim_cunoscuti=0 then necunoscuti:=true;
   boss:=b;
end;
---------------------------------------------------------
procedure sterge_pers(var m:masa_l;cod:integer);
{ sterge persoana cod de pe toate listele, de la masa m si
elimina toate legaturile ei din lista p }
var c:pers_l;
    p:pereche_l;
begin
   c:=m^.lista;
   while c^.cod<>cod do c:=c^.urm;
   c^.cod:=0; p:=p_start;
   while p<>nil do
      begin
        if (p^.cod1=cod) or (p^.cod2=cod) then
           begin
             p^.cod1:=0; p^.cod2:=0;
           end;
        p:=p^.urm;
      end;
end;
---------------------------------------------------------
procedure sterge_primul(var m:masa_l);
{ sterge prima persoana de la masa m; folosita la plecarea
prietenilor gazdei }
var n:pers_l;
begin
   n:=m^.lista^.urm;
   dispose(m^.lista);
   m^.lista:=n;
end;
----------------------------------------------------
begin { Programul principal }
   clrscr; maxim:=0; start:=nil;
   p_start:=nil; c_start:=nil;
   citeste;
   curent:=start; nr_mese:=0;
      while curent<>nil do
        begin
          inc(nr_mese); curent:=curent^.urm;
       end;
   ordoneaza; 
{aseaza mesele in ordinea crescatoare a numarului de persoane}
   p_curent:=p_start;
   curent:=start;
{ La punctul a) si b), afiseaza mesele cu liderii lor. }
   while curent<>nil do
      begin
        afiseaza_masa(curent);
writeln(', lider: ',lider(curent),', timp=',min_timp);
        curent:=curent^.urm;
      end;
   writeln('Sunt necesare ',nr_mese,' mese.');
   curent:=start;
   p_pastreaza:=p_start; 
{ pastreaza lista actuala de legaturi, pentru a fi restaurata
mai tarziu, dupa plecarea prietenilor gazdei }
   while curent^.urm<>nil do
      begin
        inc(maxim); 
{ prietenii gazdei sunt numerotati de la maxim+1 in sus }
        a:=lider(curent); b:=lider(curent^.urm);
        insert_pereche(maxim,a,b); 
{ insereaza legaturi intre noul venit si cei doi lideri }
        insereaza_unul(curent^.urm,maxim); 
{ insereaza noul venit la ambele mese }
        insereaza_unul(curent,maxim);
writeln(a,' ',b,' noul lider : ',lider(curent^.urm));
        curent:=curent^.urm;
      end;
   writeln('Timp: ',min_timp); curent:=start;
   while curent^.urm<>nil do
      begin
        sterge_primul(curent); 
{ reface mesele dupa plecarea prietenilor gazdei }
        sterge_primul(curent^.urm); curent:=curent^.urm;
      end;
   p_curent:=p_start;
   while p_curent<>p_pastreaza do 
{reface lista de legaturi dupaplecarea prietenilor gazdei}
      begin
        p_curent:=p_curent^.urm; dispose(p_start);
        p_start:=p_curent;
      end;
   while p_curent^.urm<>nil do p_curent:=p_curent^.urm;
   p_curent^.urm:=c_start; 
{ adauga legaturile din lista c la celelalte; sunt si cele
necesare, deoarece pentru acest punct se calculeaza numarul de
cunostinte al fiecarei persoane. }
   curent:=start; maxim:=0;
   while curent<>nil do
      begin
        necunoscuti:=false; inc(maxim);
        write('Masa ',maxim,' : ');
        repeat
           a:=boss(curent);
           if not necunoscuti then
              begin
                 sterge_pers(curent,a); 
{ se vor inlatura intotdeauna persoanele cu cei mai multi
cunoscuti }
                 write(a,' ');
              end;
        until necunoscuti; 
{ pana cand nimeni nu mai cunoaste pe nimeni la masa m }
        writeln; curent:=curent^.urm;
      end;
end.

          BOI 5 (Iuliu Vasilescu):
program fibonacci;
var i,j,k,l:longint;
    a,b,c:array[1..7] of integer;
    n:integer;r:boolean;
---------------------------------------------------
function prim(x:longint):boolean;
   {Verifica daca argumentul e numar prim sau nu}
var i,k:longint;t:boolean;
begin
  t:=true;k:=round(sqrt(x));
  for i:=2 to k do if x mod i=0 then begin t:=false;i:=k; end;
  prim:=t;
end;
-------------------------------------------------------
procedure genperm(x:integer);
  {cauta recursiv intre permutarile cifrelor numarului curent
   un numar prim diferit de cel initial; in variabila "r" se
   va afla rezultatul cautarii; cautarea este abandonata la
   gasirea primului numar care satisface conditia}
var k:longint;i:integer;
begin
  if x>n then begin
    k:=0;
    for i:=1 to n do k:=k*10+c[a[i]];
    if (k<>j)and(prim(k)) then r:=true;
  end else
    for i:=1 to n do if (not r) and (b[i]=0) then begin
      b[i]:=1;
      a[x]:=i;
      genperm(x+1);
      b[i]:=0;
    end;
end;
----------------------------------------------------
begin {program principal)
  {se genereaza numerele Fibonacci si pentru fiecare se verifica
celelalte conditii}
  i:=0;j:=1;
  while i<65535 do begin
    k:=i+j;i:=j;j:=k;
    if (j>=10)and(prim(j)) then begin
       r:=false; n:=0; k:=j;
       while k>0 do begin
         inc(n); c[n]:=k mod 10; k:=k div 10  end;
      for k:=1 to n do b[k]:=0;
      genperm(1);
      if r then begin
        write(j,' ');
        for k:=1 to n do write(c[a[k]]);writeln; end;
                               end;
                    end;
end.

          BOI 6 (Iuliu Vasilescu):
           Este o problem[ clasic[ de aflare a unui drum hamiltonian minim (Cornelia
Ivasc, Mona Pruna, Bazele Informaticii clasa X, Editura Petrion 1995).
program retea;
const nmax=10;
var i,j,n:integer;
    a:array[1..nmax,1..2] of real;
    b:array[1..nmax,1..nmax] of real;
    c,cm,d:array[1..nmax] of integer;
    l,lm:real;
    f:text;
---------------------------------------------------
procedure rec(p:integer);
  {genereaza recursiv si optimizat drumurile posibile; in "c"
se retine drumul curent; in "cm" drumul minim pana la pasul
curent; in "d" varfurile folosite pana la pasul curent; analog
in "l" si "lm" lungimea curenta si lungimea minima}
var i:integer;
begin
  if (l<lm)or(lm=0) then 
     begin
       if p>n then 
         begin
           if (l<lm)or(lm=0) then begin cm:=c;lm:=l; end;
         end 
              else
     if p=1 then
        for i:=1 to n do 
          begin
            c[1]:=i;d[i]:=1;rec(2);d[i]:=0;
          end
                    else
     for i:=1 to n do if d[i]=0 then 
        begin
          c[p]:=i;d[i]:=1;l:=l+b[c[p-1],i];
          rec(p+1);
          l:=l-b[c[p-1],i];d[i]:=0;
        end;
   end;
end;
-----------------------------------------------------
begin { Programul principal }
   assign(f,'in_pl2.txt');reset(f);
   read(f,n);
   for i:=1 to n do read(f,a[i,1],a[i,2]);
{se calculeaza distantele dintre noduri}
   for i:=1 to n-1 do for j:=i+1 to n do 
      begin
      b[i,j]:=sqrt((a[i,1]-a[j,1])*(a[i,1]-a[j,1])+
         (a[i,2]-a[j,2])*(a[i,2]-a[j,2]))+10;
         b[j,i]:=b[i,j];
      end;
{se initializeaza variabilele si se lanseaza procedura
recursiva}
   lm:=0;l:=0;
   for i:=1 to n do d[i]:=0;
   rec(1);
{se afiseaza rezultatele in formatul cerut}
   writeln('Rezultate:');writeln(lm:7:2);
   for i:=1 to n-1 do
writeln(b[cm[i],cm[i+1]]:7:2,cm[i]:3,cm[i+1]:3);
end.


          BOI 7 (Iuliu Vasilescu):
program sortare;
const p:array[1..6,1..3] of
integer=((1,3,2),(1,2,3),(3,1,2),(3,2,1),(2,1,3),             
    (2,3,1));
      cu:array[1..3] of char=('B','G','C');
var s:array[1..3,1..3] of integer;
    mu,mum,km:integer;
    i,j,k:integer;
    f:text;
    n,l:integer;
begin
   assign(f,'in_pl3.txt');reset(f);read(f,n);
   writeln('Solutiile sunt:');
{Se verifica pe rand, in ordine alfabetica, fiecare posilitate
de aranjare a sticlelor, retinand-o pe cea mai avantajoasa}
   for l:=1 to n do 
      begin
         for i:=1 to 3 do for j:=1 to 3 do read(f,s[i,j]);
         km:=0;
         for k:=1 to 6 do 
            begin
               mu:=0;
               for i:=1 to 3 do for j:=1 to 3 do
               if p[k,i]<>j then mu:=mu+s[i,j];
               if (mu<mum)or(km=0) then 
                  begin
                     km:=k; mum:=mu;
                  end;
             end;
        write('  ');
        for i:=1 to 3 do write(cu[p[km,i]]);
        writeln('  ',mum);
      end;
end.

          BOI 8.(Iuliu Vasilescu)
           a) Se realizeaz[ o descompunere tip backtracking, reinndu-se soluia cu
num[rul maxim de elemente (avnd n vedere m[rimea mic[ a datelor de intrare,
soluia este rapid[ i elegant[);
           b) se realizeaz[ o marcare recursiv[ a zonelor conexe umplute cu acelai
element i se caut[ cea de dimensiune maxim[.
           c) metoda folosit[ este euristic[: la fiecare pas se g[sete p[tratul de latur[
maxim[ cu care se poate pava zona, se marcheaz[ locul unde a fost plasat i
algoritmul se reia.
           d) metoda este tot euristic[: se g[sete distana minim[ ntre elementele
zonei i fiecare dintre elementele exterioare zonei care trebuie lipit[ de zona n
discuie. Apoi, la fiecare pas elementul cel mai dep[rtat se plaseaz[ ntre elementul
cel mai apropiat i zon[, lipit de zon[.
           e) metod[ similar[ cu (d), dar se g[sete nti cea mai frecvent[ cifr[
precum i zona cea mai mare care o conine.
Not[: Pentru punctele (c),(d) i (e) sunt preferate metode euristice deoarece sunt
mult mai simplu de implementat i foarte eficiente n condiii de concurs.
           Pentru punctul (c) se poate aplica i un backtracking (care ar genera soluia
cea mai bun[), dar nu cred ca ea se justific[, avnd in vedere gradul mare de
generalitate al soluiei euristice.}
program pl4;
const nrp:array[1..12] of
integer=(2,3,5,7,11,13,17,19,23,29,31,37);
         {primele numere prime}
      vx:array[1..8] of integer=(-1, 0, 1, 1, 1, 0,-1,-1);
      vy:array[1..8] of integer=(-1,-1,-1, 0, 1, 1, 1, 0);
         {vecinii unui element}
type mat=array[0..11,0..11] of integer;
var a,b,c,k:mat; 
  {matricea initiala, cea de pct. A), cea a zonelor}
    d,e:array[1..100] of integer;
      {valoarea elem. Din fiecare zona si demensiunile ei}
    f,g:text; {fisierul de intrare si de iesire}
    zm,i,j,n,m,xd1,xd2,yd1,yd2,np,di,lp:integer;
    t:boolean;
    l:array[1..20] of integer;
----------------------------------------------------------------
function desc(n:integer):integer;
  {aflarea nr. de elemente al sumei de factori primi n}
var i,m,d:integer;
function desc1(n,p,k:integer):integer;
var i,m,d:integer;
begin
  if n=0 then d:=0
  else begin
    d:=-1;
    if k=0 then if nrp[p]<=n then d:=desc1(n-nrp[p],p,1);
    for i:=p+1 to 12 do if nrp[i]<=n then begin
      m:=desc1(n-nrp[i],i,k);
      if m>d then d:=m;
    end;
    if d>-1 then inc(d);
  end;
  desc1:=d;
end;
begin
  d:=-1;
  for i:=1 to 12 do if nrp[i]<=n then begin
    m:=desc1(n-nrp[i],i,0);
    if m>d then d:=m;
  end;
  if d<>-1 then desc:=d+1 else desc:=-1;
end;
----------------------------------------------------------
procedure marc(x,y:integer); {marcare recursiva a unei zone din
matrice umpluta cu aceeasi valoare}
var i:integer;
begin
  c[x,y]:=m;inc(e[m]);
  for i:=1 to 8 do if
(b[x,y]=b[x+vx[i],y+vy[i]])and(c[x+vx[i],y+vy[i]]<>m)
    then marc(x+vx[i],y+vy[i]);
end;
----------------------------------------------------------
function verp(x,y,l:integer):boolean;
  {verifica daca la x,y se poate plasa un patrat cu latura l,
   astfel incat sa incapa in zona aleasa, marcata cu zm}
var i,j:integer;v:boolean;
begin
  v:=true;
  for i:=0 to l-1 do for j:=0 to l-1 do if c[x+i,y+j]<>zm then
v:=false;
  if v then for i:=0 to l-1 do for j:=0 to l-1 do c[x+i,y+j]:=0;
  verp:=v;
end;
----------------------------------------------------------
procedure unire;
  {rezolvarea pct d) si e)}
var nh,i,j,k:integer;
    x,y,xh,yh,dh:array[1..100] of integer;
    xp,yp,xf,yf:integer;
------------------------------------------------------------
procedure marc1(x,y,k:integer);
  {varianta modificata a lui marc}
var i:integer;
begin
  c[x,y]:=k;
  for i:=1 to 8 do if
(b[x,y]=b[x+vx[i],y+vy[i]])and(c[x+vx[i],y+vy[i]]<>k)
    then marc1(x+vx[i],y+vy[i],k);
end;
---------------------------------------------
function dist(x1,y1,x2,y2:integer):integer;
  {afla, in matrice, distanta dintre (x1,y1) si (x2,y2)}
begin
  if abs(x2-x1)>abs(y2-y1) then dist:=abs(x2-x1)-1 else
dist:=abs(y2-y1)-1;
end;
begin
  for i:=1 to n do for j:=1 to n do if c[i,j]=zm then begin
    xp:=i;yp:=j;i:=n;j:=n;
  end;
  nh:=0;
  for i:=1 to n do for j:=1 to n do if
(b[i,j]=d[zm])and(c[i,j]<>zm) then begin
    inc(nh);x[nh]:=i;y[nh]:=j;dh[nh]:=10;
  end;
  while nh>0 do begin
    for i:=1 to n do for j:=1 to n do if c[i,j]=zm then
      for k:=1 to nh do if dist(x[k],y[k],i,j)<dh[k] then begin
        dh[k]:=dist(x[k],y[k],i,j);xh[k]:=i;yh[k]:=j;
      end;
    j:=1;k:=1;
    for i:=1 to nh do if dh[i]<=dh[j] then j:=i else if
dh[i]>dh[k] then k:=i;
    if x[j]-xh[j]<>0 then xf:=xh[j]+(x[j]-xh[j]) div
abs(x[j]-xh[j]) else xf:=xh[j];
    if y[j]-yh[j]<>0 then yf:=yh[j]+(y[j]-yh[j]) div
abs(y[j]-yh[j]) else yf:=yh[j];
    writeln(g,'(',xf,',',yf,'),(',x[k],',',y[k],')');
    i:=b[xf,yf];b[xf,yf]:=b[x[k],y[k]];b[x[k],y[k]]:=i;
    marc1(xp,yp,0);marc1(xp,yp,zm);
    nh:=0;
    for i:=1 to n do for j:=1 to n do if
(b[i,j]=d[zm])and(c[i,j]<>zm) then begin
      inc(nh);x[nh]:=i;y[nh]:=j;dh[nh]:=10;
    end;
  end;
  for i:=1 to n do for j:=1 to n do begin
    write(g,b[i,j]:3);
    if j=n then writeln(g);
  end;
end;
begin
  assign(f,'in_pl4.txt');reset(f);
  assign(g,'out.txt');rewrite(g);
  read(f,n);
  for i:=1 to n do for j:=1 to n do begin
    read(f,a[i,j]);
    b[i,j]:=desc(a[i,j]); {descomp. Fiecarui elem.}
    write(g,b[i,j]:3);
    if j=n then writeln(g);
  end;
  writeln(g);
  for i:=0 to n+1 do begin
    b[0,i]:=0;b[n+1,i]:=0;b[i,n+1]:=0;b[i,0]:=0;
    for j:=0 to n+1 do c[i,j]:=0;
  end;
  m:=0;
  for i:=1 to n do for j:=1 to n do if c[i,j]=0 then begin
    inc(m);d[m]:=b[i,j];e[m]:=0;
    marc(i,j);
{marcarea in c a fiecarei zone si memorarea in e si d a datelor
despre ea}
  end;
  zm:=1;
  for i:=1 to m do if
(e[i]>e[zm])or((e[i]=e[zm])and(d[i]<d[zm]))
    then zm:=i; {calcularea zomei de dim. Maxima}
  writeln(g,e[zm]);writeln(g,d[zm]);
  xd1:=n;xd2:=1;yd1:=n;yd2:=1;
  for i:=1 to n do for j:=1 to n do if c[i,j]=zm then begin
    if i<xd1 then xd1:=i;
    if i>xd2 then xd2:=i;
    if j<yd1 then yd1:=j;
    if j>yd2 then yd2:=j;
{calcularea dreptunghiului de dimensiuni minime in care incape}
  end;
  writeln(g,'(',xd1,',',yd1,'),(',xd2,',',yd2,')');
  writeln(g);
  di:=e[zm];k:=c;
  if xd2-xd1<yd2-yd1 then lp:=xd2-xd1+1 else lp:=yd2-yd1+1;
  np:=0;
  while di>0 do begin
    t:=true;
    for i:=xd1 to xd2-lp+1 do for j:=yd1 to yd2-lp+1 do
      if verp(i,j,lp) then begin
        inc(np);di:=di-lp*lp;
      end;
    dec(lp);
  end;
  writeln(g,np);writeln(g);
  c:=k; a:=b; unire;
  c:=k;b:=a; writeln(g);
  for i:=1 to 20 do l[i]:=0;
  for i:=1 to n do for j:=1 to n do inc(l[b[i,j]]);
  j:=1;
  for i:=1 to 20 do if l[i]>l[j] then j:=i;
  zm:=0;
  for i:=1 to m do if d[i]=j then 
     if (zm=0)or(e[zm]<e[i]) then zm:=i;
  writeln(g,d[zm]); unire; close(g);
end.

            BOI.9. (Gheorghi[ Valentin, elev Ploieti)
           Se calculeaz[ maximul dintre suma volumelor pe componentele conexe care
se obin prin suprimarea fiec[rui nod. Se consider[ apoi sursa n nodul pentru care
maximul determinat este cel mai mic. Algoritmul este polinomial.
program rezervoare;
uses crt;
var a:array[1..1000,1..2] of integer;
    n,i,j,k,min,max:integer;
    c,b:array[1..1000] of integer;
    f:text;
    mlocal,temp,minim:longint;
    tt:integer;
begin
  clrscr;
  assign(f,'input.1'); reset(f); readln(f,n);
  for i:=1 to n do readln(f,b[i]);
  for i:=1 to n-1 do readln(f,a[i,1],a[i,2]);
  close(f);
  minim:=100*n;
  for i:=1 to n do begin
     for j:=1 to n do c[j]:=j;
     for j:=1 to n-1 do
       if ((a[j,1]<>i) and (a[j,2]<>i)) then begin
                 min:=c[a[j,1]]; max:=c[a[j,2]];
                 if min>c[a[j,2]] then begin
                    min:=c[a[j,2]]; max:=c[a[j,1]] end;
                 for k:=1 to n do
                   if c[k]=max then c[k]:=min;
                                            end;
    mlocal:=0;
    for j:=1 to n do
      if j<>i then begin
         temp:=0;
         for k:=1 to n do
           if c[k]=j then temp:=temp+b[k];
           if temp>mlocal then mlocal:=temp end;
    if mlocal<minim then begin
            minim:=mlocal; tt:=i; end;
                 end;
  clrscr;
  writeln('The number of optimal source is ',tt);
  writeln('The optimal time is ',minim);
end.


          BOI 10.. (Gheorghi[ Valentin, Ploieti) 
           Problema cu numere mari este rezolvat[ ntr-un algoritm care determin[
iniial num[rul de cifre al lui p, dup[ care determin[, innd cont de inecuaia ce
trebuie satisfacut[ de p, pe rnd cifrele lui ncepnd cu cea mai din stnga
("dominanta"). Algoritmul este de complexitate polinomial[.
program Numere_mari;
uses crt;
var n,p:string;
    l:byte;
    i,k:byte;
    contor:integer;
    control:boolean;
    ast:byte;
------------------------------------------------------------
function sumita(t1,t2:string):string;
var total:string;
    suma,max,i,ast,nr1,nr2:integer;
    cif1,cif2:byte;
    error:integer;
 begin
  nr1:=length(t1); nr2:=length(t2); total:='';
  ast:=0; max:=nr1;
  if max<nr2 then max:=nr2;
  for i:=1 to max do begin
    suma:=ast;
    val(t1[nr1+1-i],cif1,error); val(t2[nr2+1-i],cif2,error);
    if i<=nr1 then suma:=suma+cif1;
    if i<=nr2 then suma:=suma+cif2;
    ast:=trunc(suma/10);
    total:=chr(48+suma-ast*10)+total;
                     end;
  if ast<>0 then total:=chr(48+ast)+total;
  sumita:=total;
 end;
------------------------------------------------------
function produs(t1,t2:string):string;
  var total,temp:string;
      nr1,nr2,cif1,cif2:byte;
      prod,i,j,error:integer;
begin
  nr1:=length(t1); nr2:=length(t2);
  total:='';
  for i:=1 to nr1+nr2 do total:=total+'0';
  for i:=1 to nr1 do begin
     temp:=''; ast:=0;
     for j:=1 to nr2+1 do temp:=temp+'0';
     for j:=nr2 downto 1 do begin
       val(t1[nr1-i+1],cif1,error); val(t2[j],cif2,error);
       prod:=cif1*cif2+ast;
       ast:=trunc(prod/10);
       temp[j+1]:=chr(48+prod-ast*10);
                            end;
    temp[1]:=chr(ast+48);
    for j:=1 to i-1 do temp:=temp+'0';
    total:=sumita(total,temp);
                    end;
 nr1:=length(total);
 if total[1]='0' then begin
       temp:='';
       for i:=2 to nr1 do temp:=temp+total[i];
       total:=temp  end;
  produs:=total;
 end;
----------------------------------------------------------
procedure functie;
var s1,s2,s3,s4:string;
    i:integer;
    mm:boolean;
begin
  s1:=produs('3',p); s2:=produs(p,p); s3:=produs(p,s2);
  s4:=sumita(sumita(s1,s2),s3);
  if length(s4)>k then control:=true;
  if length(s4)=k then begin
      mm:=false;
      for i:=1 to k do
         if not(mm) then begin
            if s4[i]<>n[i] then mm:=true;
            if s4[i]>n[i] then control:=true
                     end  end
end;
-----------------------------------------------------
begin
  clrscr;
  write('Introduceti n : '); readln(n);
  k:=length(n); l:=trunc((k+2)/3); p:='';
  for i:=1 to l do p:=p+'0';
  contor:=0; control:=false;
  repeat
    contor:=contor+1; p[1]:=chr(48+contor);
    functie;
  until ((control) or (contor=9));
  if control then p[1]:=chr(48+contor-1);
  if p[1]='0' then p[1]:='1';
  for i:=2 to l do begin
   contor:=-1; control:=false;
   repeat
     contor:=contor+1; p[i]:=chr(48+contor);
     functie;
   until ((control) or (contor=9));
   if ((control) and (p[i]<>'0')) then p[i]:=chr(48+contor-1);
                   end;
  control:=false; functie;
  if control then begin
     p:='';
     for i:=1 to l-1 do p:=p+'9';
                  end;
 writeln('Numarul p este ',p);
 repeat until keypressed;
end.


          BOI 11. (Gheorghi[ Valentin, Ploieti)
Se folosete un backtracking recursiv.
program clienti;
uses crt;
var f:text;
    n:byte;
    a:array[1..50,1..2] of byte;
    salv:array[1..50] of byte;
    min,i:integer;
-------------------------------------------------------
procedure recurs(poz,suma,etaj:integer);
var i,j,s:integer;
    val:boolean;
 begin
   if poz=n+1 then min:=suma;
              else for i:=1 to n do begin
      val:=true; s:=suma;
      for j:=1 to poz-1 do
        if i=salv[j] then val:=false;
        if a[i,1]>etaj then s:=s+a[i,1]-etaj;
        if a[i,1]<a[i,2] then s:=s+a[i,2]-a[i,1];
        if s>=min then val:=false;
        if val then begin
           salv[poz]:=i; recurs(poz+1,s,a[i,2]);
                    end;
                                   end;
end;
--------------------------------------------------------
begin
  clrscr;
  assign(f,'input.3'); reset(f); readln(f,n);
  for i:=1 to n do readln(f,a[i,1],a[i,2]);
  close(f);
  min:=n*9; recurs(1,0,1);
 writeln(min);
 repeat until keypressed;
end.

          BOI 12: (C[t[lin Frncu - Bucureti)
program meciuri;
  const MaxTeams=250;
  type ByteMatrix=array[1..MaxTeams,1..MaxTeams] of Byte;
  var RealN,N:Integer;
      A:ByteMatrix;
----------------------------------------------
procedure ReadData;
var i,j:Integer;
begin
   Write('Numarul de echipe (2-250): ');
   ReadLn(RealN);
   if RealN mod 2=1 then N:=RealN+1
        else N:=RealN;  { Se simuleaza un numar par de echipe}
   for i:=1 to N do
     for j:=1 to N do A[i,j]:=0;
end;
------------------------------------------------------------
procedure FindNextFree(K:Integer;var j:Integer);
{ Parcurge circular linia K a matricii pina cind gaseste un 0}
begin
  repeat
    Inc(j);
    if j=N then J:=1;
  until A[K,j]=0;
end;
----------------------------------------------------------------
procedure AddLine(K:Integer);
{ Stabileste meciurile echipei K. Aceasta are deja stabilite me-
ciurile cu echipele 1..K-1, iar pe cele cu K+1..N trebuie sa le
stabileasca astfel incit sa nu se suprapuna peste alte cereri}
var i,j:Integer;
begin
  j:=0;
  repeat Inc(j) until A[K,j]=K-1;
    { gaseste etapa in care a avut loc meciul K<->K-1 }
  FindNextFree(K,j);
  for i:=K+1 to N do
    begin
      FindNextFree(K,j);
      A[K,j]:=i; A[i,j]:=K;
    end;
end;
--------------------------------------------------------
procedure FillMatrix;
var i,j:Integer;
begin
  for i:=1 to N-1 do begin
   A[1,i]:=i+1; 
{ Prima echipa isi programeaza meciurile la alegere }
      A[i+1,i]:=1;
    end;
  for i:=2 to N-1 do AddLine(i);
  if RealN<>N then 
     for i:=1 to N-1 do
        for j:=1 to N-1 do
         if A[i,j]=N then A[i,j]:=0; { N este o "dummy-team" }
end;
--------------------------------------------------------
procedure WriteSolution;
var i,j:Integer;
begin
  for i:=1 to RealN do
    begin
      for j:=1 to RealN-1 do Write(A[i,j]:3);
      if RealN<>N then Write(A[i,RealN]:3);
      WriteLn;
    end;
end;
-------------------------------------------------------------
begin
  ReadData;
  FillMatrix;
  WriteSolution;
end.

            BOI 13. (Vlad Petric, elev Braov)
Ideea principal[ de lucru este backtrackingul, numai c[ parcugerea se face eficient,
adic[ dup[ ce un nod este marcat, se continu[ marcarea cu nodurile adiacente
acestuia. Cum sistemul este conex, vor fi parcurse toate nodurile.
const dim=250;
var graf:array[1..dim,1..dim] of boolean;
    dm,n,m,p:byte;
    s:char;
    sir,sm:array[1..dim] of char;
-----------------------------------------------
function posibil(p:byte;ch:char):boolean;
var i:byte;
begin
  for i:=1 to n do
    if graf[i,p] and (sir[i]=ch) then begin
      posibil:=false;
      exit;
    end;
  posibil:=true;
end;
-------------------------------------------
procedure backtrack(p,count,el:byte);
var i:byte;
begin
  if el<dm then
    if count=n  then begin
      dm:=el; sm:=sir end
    else
      for i:=1 to n do
        if (sir[i]=' ') and graf[i,p] then begin
          if posibil(i,'C') then begin
            sir[i]:='C';
            backtrack(i,count+1,el);
          end;
          if posibil(i,'O') then begin
            sir[i]:='O';
            backtrack(i,count+1,el);
          end;
          sir[i]:='R';
          backtrack(i,count+1,el+1);
          sir[i]:=' ';
        end;
end;
----------------------------------------
procedure tratare;
var i:byte;
    aux:boolean;
begin
  sir[p]:=s; dm:=n;
  backtrack(p,1,0);
  sir:=sm; aux:=true;
  for i:=1 to n do
    if sir[i]='R' then aux:=false;
  if aux then writeln('W')
         else writeln('B');
  write('C ');
  for i:=1 to n do
    if sir[i]='C' then
      write(i,' '); writeln; write('O ');
  for i:=1 to n do
    if sir[i]='O' then write(i,' ');
  writeln;
  if not aux then begin
    write('R ');
    for i:=1 to n do
      if sir[i]='R' then write(i,' ');
    writeln;
  end;
end;
----------------------------------------------
procedure citire;
var f:text;
    nf:string;
    i,j,a,b:byte;
    ss:char;
begin
  writeln('Nume fisier:'); readln(nf);
  assign(f,nf); reset(f); readln(f,n,m);
  for i:=1 to n do begin
    sir[i]:=' ';
    for j:=1 to n do
      graf[i,j]:=false;
  end;
  for i:=1 to m do begin
    readln(f,a,b); graf[a,b]:=true; graf[b,a]:=true;
  end;
  readln(f,p,ss,s); close(f);
end;
--------------------------------
begin {Program principal}
  citire;
  tratare;
end.

 
            BOI.16. (Mihai B[doiu)
program Inflorescenta;
var
        n:integer;
        s,s2: string;
        x:char;
        v:string;
---------------------------------------------------------
function egal(a:integer):boolean;
var
        i:integer;
begin
   egal:=false;
   for i:=a to a+length(s2)-1 do
     if (s2[i-a+1]<>x) and (v[i]<>s2[i-a+1]) then exit;
   egal:=true;
end;
----------------------------------------------------------
function gaseste:integer;
var
        i:integer;
begin
   for i:=1 to length(v)-length(s2)+1 do
      if egal(i) then begin
         gaseste:=i; exit end;
   gaseste:=0;
end;
---------------------------------------------------------
procedure calcul;
var
        j:integer;
begin
  repeat
    j:=gaseste;
    if j<>0 then
      v:=copy(v,1,j-1)+x+copy(v,j+length(s2),
         length(v)-j+length(s2)+1);
  until j=0;
  if (length(v)=1) and (v[1]=x) then 
    writeln('este o floare')
    else writeln('NU este o floare')
end;
-------------------------------------------------
procedure load;
var
        f:text;
begin
   assign(f,'p3.in'); reset(f);
   readln(f,n); readln(f,s);  {OOOOps....}
   readln(f,x); readln(f,s2);
   close(f); write('v=');
   readln(v);
   calcul;
end;
---------------------------------------------------------
begin
   load;
end.


            BOI.19. (Adrian Atanasiu)
           Soluia este foarte simpl[ i se reduce la determinarea num[rului maxim
de segmente care se suprapun; este clar c[ numai n acest caz sunt necesare culori
diferite pentru a le distinge.
           Axa pe care sunt scrise segmentele este tabloul linie. Elementele lui sunt
iniial 0 (nu are nici un segment); fiecare segment se coloreaz[ adunnd elementele
sale din linie cu 1. Dac[ de exemplu exist[ un element k al liniei cu linie[k]:=
4, aceasta nseamn[ ca linie[k] este parte component[ a patru segmente - deci
aceste segmente necesit[ patru culori diferite pentru a fi distinse.
program colorare;
uses crt;
var
  linie: array[1..1000] of integer;
  a,b,max,i,j,n:integer;
begin
  clrscr;
  write('dati numarul de segmente. n=');readln(n);
  for i:=1 to 1000 do linie[i]:=0;
  for i:=1 to n do begin
      readln(a,b);
      for j:=a+1 to b do linie[j]:=linie[j]+1
                   end;
  max:=0;
  for i:=1 to 1000 do
     if max<linie[i] then max:=linie[i];
  writeln('Numarul maxim de culori necesare este ',max);
end.


          BOI.20. (Adrian Atanasiu):
           Completarea tabelului se face folosind urm[torul program, care pentru
fiecare x determin[ num[rul de zerouri cu care se termin[ x!=1*2*..*x;
formula dup[ care se determin[ num[rul N de zerouri este
N=[x/5]+[x/5^2]+[x/5^3]+...
program cifre;
uses crt;
var 
   i,j,k,x,fac:integer;
begin
  clrscr;
  for i:=0 to 9 do begin
    for j:=0 to 9 do begin
       x:=10*i+j; fac:=0; k:=5;
       while (x div k)>0 do begin
          fac:=fac+(x div k);
          k:=k*5 end;
       write(fac,'  ')
                     end;
    writeln end;
end.


                      BOI.21. (Mihai B[doiu)
program Interviu;
const
        max=100;
var
        v:array[1..max,1..max] of byte;
        t:array[1..max] of byte;
        total,n:integer;
-----------------------------------------------------
procedure scrie;
begin
        writeln('Total =',total);
end;
---------------------------------------------------------
procedure approximation_algorithm2;
var
        i,j:integer;
        io,jo,so:integer;
begin
 repeat
  so:=0;
  for i:=1 to n do
    for j:=i+1 to n do
     if so<v[t[i],j]+v[t[j],i]-v[t[i],i]-v[t[j],j] then
                        begin
       so:=v[t[i],j]+v[t[j],i]-v[t[i],i]-v[t[j],j];
       io:=i; jo:=j;
                        end;
     if so<>0 then begin
        total:=total+v[t[io],jo]+v[t[jo],io]-
            v[t[io],io]-v[t[jo],jo];
        i:=t[io]; t[io]:=t[jo]; t[jo]:=i;
                   end;
 until so=0;
end;
-------------------------------------------------------
function approximation_algorithm3:boolean;
var
        i,j,k:integer;
        io,jo,ko,so:integer;
begin
   approximation_algorithm3:=true;
   repeat
     so:=0;
     for i:=1 to n do
        for j:=i+1 to n do
           for k:=i+1 to n do
             if j<>k then begin
  if so<v[t[i],j]+v[t[j],k]+v[t[k],i]-
        v[t[i],i]-v[t[j],j]-v[t[k],k] then begin
           so:=v[t[i],j]+v[t[j],k]+v[t[k],i]-            
              v[t[i],i]-v[t[j],j]-v[t[k],k];
           io:=i; jo:=j; ko:=k;
                                           end;
                          end;
   if so<>0 then begin
     total:=total+v[t[io],jo]+v[t[jo],ko]+v[t[ko],io]-
          v[t[io],io]- v[t[jo],jo]-v[t[ko],ko];
     i:=t[ko]; t[ko]:=t[jo]; t[jo]:=t[io]; t[io]:=i;
     approximation_algorithm3:=false;
                 end;
  until so=0;
end;
---------------------------------------------------------
procedure calcul;
var
        i:integer;
begin
  total:=0;
  for i:=1 to n do begin
    t[i]:=i; inc(total,v[i,i]);
                   end;
  repeat
     approximation_algorithm2;
  until approximation_algorithm3;
end;
-----------------------------------------------------
procedure load;
var
        f:text;
        i,j:integer;
begin
  assign(f,'p5.in');
  reset(f);
  while not eof(f) do begin
     readln(f,n);
     for j:=1 to n do begin
        for i:=1 to n do read(f,v[j,i]);                 
        readln(f);
                      end;
     calcul;
     scrie;
                     end;
  close(f);
end;
-----------------------------------------
begin
   load;
end.


            BOI.22. (Mihai B[doiu)
program servire; 
const
        max=100;
var
        v: array[1..20] of record
                nr, n: integer;
                l: array[0..max] of record
                        prior,pas:integer;
                        end;
                end;
        vn: integer;
        vn_old: integer;
        sel: integer;
        pasg: integer;
----------------------------------------------------------
procedure insertl(a,b:integer);
var
        i,k:integer;
begin
   k:=0;
   for i:=1 to vn do
      if v[i].nr=a then begin k:=i; break end;
   if k=0 then begin
     inc(vn); k:=vn;
     v[k].n:=0; v[k].nr:=a; v[k].l[0].prior:=-maxint-1;
     v[k].l[0].pas:=pasg;
               end;
  inc(v[k].n); i:=v[k].n-1;
  for i:=v[k].n-1 downto 0 do
     if v[k].l[i].prior>b then begin
          v[k].l[i+1]:=v[k].l[i] end
                          else break;
  v[k].l[i+1].prior:=b;
  v[k].l[i+1].pas:=pasg;
end;
---------------------------------------------------------
procedure extrage(k:integer);
var
        i:integer;
begin
   for i:=1 to v[k].n do v[k].l[i]:=v[k].l[i+1];
   dec(v[k].n);
end;
-----------------------------------------------------
procedure select_out;
var
        i: integer;
begin
  if vn>vn_old then begin
     inc(vn_old);
     writeln(v[vn_old].nr:5,v[vn_old].l[1].prior:5,
        v[vn_old].l[1].pas:5);
     extrage(vn_old);
     exit;
                end;
  for i:=sel to vn do
    if v[i].n>0 then begin
 writeln(v[i].nr:5,v[i].l[1].prior:5,v[i].l[1].pas:5);
       extrage(i); sel:=i+1; exit;
                     end;
    for i:=1 to vn do
      if v[i].n>0 then begin
 writeln(v[i].nr:5,v[i].l[1].prior:5,v[i].l[1].pas:5);
        extrage(i); sel:=i+1; exit;
                       end;
end;
---------------------------------------------
procedure calcul;
var
        f:text;
        a,b,i,n:integer;
begin
  sel:=1; pasg:=1;
  assign(f,'p6.in'); reset(f);
  repeat
    read(f,n);
    for i:=1 to n do begin
       read(f,a,b); insertl(a,b); end;
       select_out; inc(pasg);
       readln(f);
  until n=-1;
  close(f);
end;
---------------------------------------------------------
begin
   writeln;
   calcul;
end.

                      BOI.23.
program Siluete; 
const
        max=100;
var
        n:integer;
        v:array[1..21] of record
                a,b:integer;
                h:array [-1..max+1] of record
                        low,high: integer;
                        end;
                end;
----------------------------------------------------
procedure traseaza(c,a,b,h:integer);
var
        i,j:integer;
begin
  for i:=a to b do begin
    v[c].h[i].high:=h; v[c].h[i].low:=0 end;
    if v[c].a>a then v[c].a:=a;
    if v[c].b<b then v[c].b:=b;
    for j:=1 to c-1 do
      for i:=a to b do
        if v[j].h[i].low<h then begin
           v[j].h[i].low:=h;
           if v[j].h[i].low>v[j].h[i].high then
              v[j].h[i].high:=v[j].h[i].low;
                                end;
end;
--------------------------------------------------
procedure calcul;
var
        i,j,k,kp,polilinii: integer;
        s:integer;
begin
  kp:=0; polilinii:=0; s:=0;
  for j:=0 to max do begin
     k:=0;
     for i:=n downto 1 do
       if v[i].h[j].high>k then k:=v[i].h[j].high;
    if (k<>0) and (s=0) then inc(polilinii);
    s:=k;
                    end;
 writeln(polilinii:5);
{*** calcul polilinii ***}
 s:=0;
 for j:=0 to max do begin
   k:=0;
   for i:=n downto 1 do
     if v[i].h[j].high>k then k:=v[i].h[j].high;
   if (k=0) and (s<>0) then writeln(j:5)
                       else
      if k<>s then write(j:5,k:5);
   s:=k;
                   end;
{*** Cladiri vizibile ***}
 for i:=1 to n do
    for j:=v[i].a to v[i].b do
      if v[i].h[j].high>v[i].h[j].low then begin
          write(i:5); break end;
 writeln;
{*** Arii ***}
 s:=0;
 for i:=1 to n do begin
   k:=0;
   for j:=v[i].a to v[i].b do
     if not( (v[i].h[j-1].low>=v[i].h[j].high) or
         (v[i].h[j-1].high<=v[i].h[j].low))
        then k:=k+v[i].h[j].high-v[i].h[j].low
        else begin
          if s<k then s:=k;
          k:=v[i].h[j].high-v[i].h[j].low;
             end;
   if s<k then s:=k;
                 end;
 writeln(s:5);
end;
------------------------------------------------
procedure init;
var
        i,j:integer;
begin
  for i:=1 to 21 do
    for j:=-1 to max+1 do begin
      v[i].h[j].low:=0; v[i].h[j].high:=0;
                          end;
end;
--------------------------------------------------------
procedure load;
var
        f:text;
        i,j,a,b:integer;
begin
  assign(f,'p7.in'); reset(f);
  while not eof (f) do begin
     init;
     readln(f,n);
     for i:=1 to n do begin
        read(f,j);
        v[i].a:=maxint; v[i].b:=-maxint-1;
        while not eoln(f) do begin
           read(f,a,b);
           traseaza(i,j,b-1,a);
           j:=b   end;
        readln(f);
                      end;
    calcul;
                 end;
  close(f);
end;
-------------------------------------------------
begin
   writeln;
   load;
end.








            Alte soluii:

            BOI.1. (Vlad Atanasiu)
Programul a fost construit cu preciz[ri comentate pentru a urm[ri uor algoritmul
folosit.
uses crt;
type punct=record
           x,y:integer;
           end;
     list=^lst;
     lst=record
         p:punct;
         urm:list;
         end;
     cap_lista=^caplista;
     caplista=record
               nr_puncte:integer;
               urm:cap_lista;
               lista:list;
               end;
     grila=record
                 tb:array[1..100,1..100] of byte;
                 dimx,dimy:integer;
           end;
var minx,maxx,miny,maxy,arie_min,nrmaxim,i,j:integer;
    tablou:grila;
    cmm,primalista,cl,cap:cap_lista;
    pct:punct;
-------------------------------------------------------
function trebuie_adaugat(l:list;c:punct):boolean;
          {Intoarce true daca punctul are un vecin in lista L}
var tmp:boolean;
begin
   tmp:=false;
   while (l<>nil) and (not tmp) do
      if (abs(l^.p.x-c.x)<2) and (abs(l^.p.y-c.y)<2) 
           then tmp:=true else l:=l^.urm;
   trebuie_adaugat:=tmp;
end;
---------------------------------------------------------
procedure adauga_punct(var l:cap_lista;c:punct);
{ Adauga un punct la o lista si mareste nrmaxim daca
nrpuncte>nrmaxim atunci nrmaxim=nrpuncte }
var listatmp:list;
begin
   listatmp:=l^.lista; new(l^.lista);
   l^.lista^.p:=c; l^.lista^.urm:=listatmp;
   inc(l^.nr_puncte);
   if l^.nr_puncte>nrmaxim then nrmaxim:=l^.nr_puncte;
end;
---------------------------------------------------------------
procedure afiseaza_lista(cl:cap_lista);
var f:list;
begin
   f:=cl^.lista;
   while f<>nil do
      begin
         write('(',f^.p.x,',',f^.p.y,')');
         f:=f^.urm;
      end;
   writeln('are ',cl^.nr_puncte,' puncte. ');
end;
--------------------------------------------------------
procedure reuniune(var lista1,lista2:cap_lista);
{ Adauga lista2 la lista1 si sterge lista2 }
var listatmp:list;
begin
   listatmp:=lista1^.lista;
   if listatmp<>nil then while listatmp^.urm<>nil do
      listatmp:=listatmp^.urm;
   listatmp^.urm:=lista2^.lista;
   lista1^.nr_puncte:=lista1^.nr_puncte+lista2^.nr_puncte;
   lista2^.lista:=nil;
   lista2^.nr_puncte:=0;
   if lista1^.nr_puncte>nrmaxim then nrmaxim:=lista1^.nr_puncte;
end;
-------------------------------------------------------
procedure citeste(var g:grila);
{Se citeste grila, pe coloane. Cand se va face referire la un
punct, prima coordonate data va fi y si dupa aceea x}
var input:text;
   i,j:integer;
   s:string;
begin
   assign(input,'input');
   reset(input);
   readln(input,g.dimx,g.dimy);
   for i:=1 to g.dimy do
      begin
         for j:=1 to g.dimx do read(input,g.tb[i,j]);
         readln(input);
      end;
   close(input);
end;
---------------------------------------------------------
procedure afiseaza(var g:grila);
var i,j:integer;
begin
   writeln('Dim.: ',g.dimy,' linii, ',g.dimx,'coloane.');
   for i:=1 to g.dimy do
      begin
         for j:=1 to g.dimx do write(g.tb[i,j],' ');
         writeln;
      end;
end;
--------------------------------------------------
procedure init_cap_lista(var cl:cap_lista);
begin
   cl:=new(cap_lista);
   cl^.nr_puncte:=0; cl^.lista:=nil; cl^.urm:=nil;
end;
----------------------------------------------------
function arie(l:list):integer; 
{functia intoarce arie dreptunghiului care poate incadra  
obiectul din lista l }
begin
   minx:=l^.p.x; miny:=l^.p.y; maxx:=l^.p.x; maxy:=l^.p.y;
   while l<>nil do
      begin
        if l^.p.x>maxx then maxx:=l^.p.x;
        if l^.p.x<minx then minx:=l^.p.x;
        if l^.p.y>maxy then maxy:=l^.p.y;
        if l^.p.y<miny then miny:=l^.p.y;
        l:=l^.urm;
      end;
   arie:=(maxx-minx+1)*(maxy-miny+1);
end;

function se_poate(i,j:integer):boolean;
{ functia intoarce True daca la coordonatele i,j se poate pune
obiectul maximal fara sa altereze alte obiecte deja existente.}
var l:list; sepoate:boolean;
begin
   l:=cmm^.lista; sepoate:=true;
   while (l<>nil) and (sepoate) do
      begin
    if f^tablou.tb[l^.p.y-miny+i,l^.p.x-minx+j]=1 
       then sepoate:=false; l:=l^.urm;
      end;
   se_poate:=sepoate;
end;
---------------------------------------------------------
procedure aseaza(i,j:integer);
{ pune obiectul maximal in grila la pozitia i,j }
var l:list;
begin
   l:=cmm^.lista;
   while l<>nil do
      begin
        tablou.tb[l^.p.y-miny+i,l^.p.x-minx+j]:=1;
        l:=l^.urm;
      end;
end;
------------------------------------------------------
begin { PROGRAMUL PRINCIPAL }
   clrscr;
   cap:=nil; nrmaxim:=0;
   citeste(tablou);
      { pentru fiecare punct }
   for pct.y:=1 to tablou.dimy do for pct.x:=1 to
      tablou.dimx do
       { daca este 1 atunci }
     if tablou.tb[pct.y,pct.x]=1 then
        begin
           primalista:=nil; 
{ punctul inca nu a fost adaugat nicaieri, asa ca prima lista
in care va fi adaugat nu e inca cunoscuta }
            { pentru fiecare cap_lista }
           cl:=cap;
           while cl<>nil do
              begin
             { daca trebuie adaugat in lista respectiva }
                if trebuie_adaugat(cl^.lista,pct) then
                   begin
{ daca inca nu a fost adaugat nicaieri prima lista ia         
 valoarea listei curente}
                     if primalista=nil then
                        begin
                           primalista:=cl;
{ daca lista curenta nu este prima lista la care a fost
  adaugat punctul, o concateneaza cu prima lista }
{ adauga punct la doar la prima lista }
                           adauga_punct(cl,pct);
                        end
                          else reuniune(primalista,cl);
                   end;
                cl:=cl^.urm;
              end;
            { daca nu a fost adaugat la nici o lista }
            if primalista=nil then
               begin
{se creeaza un nou cap_lista care contine o lista }
                 cl:=cap; init_cap_lista(cap);
                 cap^.urm:=cl;
{ adauga_punct la lista nou creeata }
                 adauga_punct(cap,pct);
              end;
            end;
   cl:=cap;
{ vom inmagazina in cmm pointerul spre obiectul cu cel mai    
mare numar de elemente si care este incadrat intr-un
   dreptunghi de arie minima }
   cmm:=cap; arie_min:=tablou.dimx*tablou.dimy;
{ pentru fiecare obiect }
   while cl<>nil do
      begin
{ daca numarul de elemente este maxim si aria obiectului
    este mai mica decat aria minima }
       if (cl^.nr_puncte=nrmaxim) and 
          (arie(cl^.lista)<arie_min) then
          begin
{ reactualizeaza variabilele }
             cmm:=cl; arie_min:=arie(cl^.lista);
          end;
       cl:=cl^.urm;
     end;
   writeln('Obiectul cautat este ');
   afiseaza_lista(cmm);
   writeln('Poate fi incadrat intr-un dreptunghi cu aria
           de',arie_min,' puncte.');
   write('Asezarea optima a obiectului: ');
   for i:=1 to tablou.dimy-maxy+miny do
      for j:=1 to tablou.dimx-maxx+minx do
         if se_poate(i,j) then
            begin
              write('(',i,',',j,')'); aseaza(i,j);
            end;
   writeln; writeln('Grila a devenit :');afiseaza(tablou);
end.

          BOI.5. (Vlad Atanasiu)
uses crt;
type numar=array[1..5] of byte;
var fi1,fi2, { folosesc pentru dezvoltarea Fibonacci }
    x,xn:longint;
    a,b:numar; {in vectorul a se memoreaza indexul iar in b
numarul }
    i,dig:byte;
    gasit,sfarsit:boolean;
---------------------------------------------------------
function fibonacci:longint; 
{ intoarce urmatorul termen din sirul Fibonacci }
var x:longint;
begin
   x:=fi1+fi2; { calculeaza termenul }
   fi2:=fi1;  { actualizeaza fi1 si fi2 }
   fi1:=x; fibonacci:=x;
end;
---------------------------------------------------------
procedure permuta(n:integer); 
{ procedura modifica vectorul a astfel incat sa contina
urmatoarea permutare posibila. x este numarul de digiti pentru
care se calculeaza permutarea; de exemplu, la numere de 3 cifre
se vor calcula doar permutarile de 3 (1x2x3=6 permutari) .}
var i,x,j,k,min,minx:integer;
begin
   i:=n;
   if i=1 then
     begin
       sfarsit:=true; i:=0;
     end;
   while i>1 do
     if a[i]>a[i-1] then
       begin
         min:=5; minx:=1;
         for k:=i to n do
            if (a[k]>a[i-1]) and (a[k]-a[i-1]<min) then
               begin
                 min:=a[k]-a[i-1]; minx:=k;
               end;
        x:=a[minx]; a[minx]:=a[i-1]; a[i-1]:=x;
        for k:=n-1 downto i do
           for j:=i to k do
              if a[j]>a[j+1] then
                 begin
                   x:=a[j]; a[j]:=a[j+1]; a[j+1]:=x;
                 end;
       i:=0;
     end
                    else 
     begin
       dec(i);
       if i=1 then sfarsit:=true;
     end;
end;
---------------------------------------------------------
function xtoa(x:longint;var a:numar):integer;
{ functia realizeaza transferul digitilor lui x in vectorul a
}
var nrd:integer;
    b:numar;
begin
   nrd:=1;
   while x<>0 do
      begin
        b[nrd]:=x mod 10;
        x:=x div 10; inc(nrd);
      end;
   xtoa:=nrd-1; 
   for i:=1 to nrd do a[i]:=b[nrd-i];
end;
---------------------------------------------------------
function new_number(var a,b:numar;nrd:byte):longint; 
{ procedura construieste permutarea numarului aflat in vectorul
b in functie de indecsii din a, si il intoarce ca valoare
longint. }
var i:integer;
    x:longint;
begin
   x:=0;
   for i:=1 to nrd do x:=10*x+b[a[i]];
{ exemplu: daca numarul este 54231 iar indexul 14253 numarul
construit va fi 53412 }
   new_number:=x;
end;
---------------------------------------------------------
function prim(x:longint):boolean; { intoarce True daca x este
prim }
var i:longint;
    gasit:boolean;
begin
   if x mod 2=0 then gasit:=true 
{se elimina din start numerele pare}
                else gasit:=false;
   i:=3; { se incepe cu 3 testul de divizibilitate }
   while (i<x div 2) and not gasit do
      begin
        if x mod i=0 then gasit:=true;
        i:=i+2; {si se avanseaza numai in numere impare}
      end;
   prim:=not gasit; 
{numarul este prim daca nu a fost gasit nici un divizor }
end;
---------------------------------------------------------
begin { Programul principal }
   clrscr; fi1:=1; fi2:=1;
   x:=1; 
{se incepe cu al doilea termen de 1 din sirul Fibonacci }
   while x<65535 do begin
        sfarsit:=false; 
{sfarsit va lua valoarea True cand vor fi incheiate toate
permutarile}
        gasit:=false; 
{ gasit va lua valoarea True cand se va gasi o permutare din
care sa rezulte un numar prim }
        dig:=xtoa(x,b);  
{ transfera numarul digit cu digit in vectorul b }
        for i:=1 to 5 do a[i]:=i; 
{ a contine pentru inceput permutarea identica, care NU va fi
analizata (inainte de orice analiza se trece la urmatoarea
permutare) }
        while (not sfarsit) and (not gasit) do
           begin
    repeat permuta(dig) until (a[dig] mod 2=1) or sfarsit;
{ elimina din start permutarile divizibile cu 2 }
             xn:=new_number(a,b,dig); 
{ construieste numarul rezultat in functie de permutarea
obtinuta anterior }
    if prim(xn) and (not sfarsit) then gasit:=true;
{ daca este prim anunta ca a gasit un numar prim si iese din
ciclu }
            end;
      if gasit then writeln(x,' - ',xn); 
{ daca s-a gasit o permutare prima se afiseaza numarul si
permutarea}
      repeat x:=fibonacci until (prim(x) or (x>65535));
      { se calculeaza urmatorul numar prim Fibonacci }
    end;
end.

          BOI.6. (Vlad Atanasiu)
uses crt;
type numar=array[1..101] of byte;
     punct=record
                 x,y:integer;
           end;
var c:array[1..100,1..100] of real;
    s:array[1..100] of boolean;
    solutie,solutie_finala:numar;
    drum_minim,minim,maxim:real;
  pozitie,poz_finala,nod_curent,nod_apropiat,
          nc,i,j,n:integer;
---------------------------------------------------------
procedure citeste;
{ citeste datele de intrare din fisierul 'input50' }
var t:text;
    i,j:integer;
    coordonate:array[1..100] of punct;
begin
   assign(t,'input50'); 
{ datele se citesc din fisierul 'input50' }
   reset(t); readln(t,n);
   for i:=1 to n do
      begin
        read(t,coordonate[i].x);
        readln(t,coordonate[i].y);
     end;
   for i:=1 to n do   
{Se determina matricea C a drumurilor}
   for j:=i+1 to n do
      begin
        c[i,j]:=sqrt(sqr(coordonate[i].x-coordonate[j].x)+
                   sqr(coordonate[i].y-coordonate[j].y));
        c[j,i]:=c[i,j];
      end;
   close(t);
end;
---------------------------------------------------------
function min(x,y:real):real;
begin
   min:=y;
   if y>x then min:=x;
end;
---------------------------------------------------------
begin { Programul principal }
   clrscr;
   citeste; drum_minim:=1500;
   for nc:=1 to n do
      begin
        nod_curent:=nc;
        for i:=1 to n do s[i]:=true;
        solutie[1]:=nod_curent; s[nod_curent]:=false;
        for i:=2 to n do
          begin
{cauta nodul cel mai apropiat de nodul curent si care nu a fost
marcat}
            minim:=1500;
            for j:=1 to 100 do
              if s[j] and (c[nod_curent,j]<=minim) then
                 begin
                nod_apropiat:=j; minim:=c[nod_curent,j];
                 end;
            s[nod_apropiat]:=false;
{ marcheaza nodul gasit ca fiind folosit }
            solutie[i]:=nod_apropiat; 
{ noteaza nodul gasit in vectorul solutie }
            nod_curent:=nod_apropiat; 
{ nodul gasit devine nod curent}
          end;
    maxim:=0; 
{cauta distanta maxima dintre doua puncte consecutive din
vectorul solutie }
    solutie[n+1]:=nc;
    pozitie:=1;
    for i:=1 to n do
       if c[solutie[i],solutie[i+1]]>maxim then
          begin
             maxim:=c[solutie[i],solutie[i+1]];
             pozitie:=i;
          end;
    maxim:=0; { maxim va contine drumul total }
    for i:=pozitie+1 to n do
       maxim:=maxim+10+c[solutie[i],solutie[i+1]];
    for i:=1 to pozitie-1 do
       maxim:=maxim+10+c[solutie[i],solutie[i+1]];
    if maxim<drum_minim then
      begin
         solutie_finala:=solutie; drum_minim:=maxim;
         poz_finala:=pozitie;
      end;
    end;
   writeln('Drum total : ',drum_minim:6:3);
   for i:=poz_finala+1 to n do 
    writeln(solutie_finala[i]:2,' - ',solutie_finala[i+1]:2,' 
',10+c[solutie_finala[i],solutie_finala[i+1]]:6:3);
   for i:=1 to poz_finala-1 do 
      writeln(solutie_finala[i]:2,' - ', solutie_finala[i+1]:2,' 
 ',10+c[solutie_finala[i],solutie_finala[i+1]]:6:3);
end.

          BOI.8. (Iuliu Vasilescu)
program pl4;
const nrp:array[1..12] of integer=(2,3,5,7,11,13,17,19,23,29,31,37);
      vx:array[1..8] of integer=(-1, 0, 1, 1, 1, 0,-1,-1);
      vy:array[1..8] of integer=(-1,-1,-1, 0, 1, 1, 1, 0);
type mat=array[0..11,0..11] of integer;
var a,b,c,k:mat;
    d,e:array[1..100] of integer;
    f,g:text;
    zm,i,j,n,m,xd1,xd2,yd1,yd2,np,di,lp:integer;
    t:boolean;
    l:array[1..20] of integer;
--------------------------------------------------
function desc(n:integer):integer;
var i,m,d:integer;
---------------------------------------------------
function desc1(n,p,k:integer):integer;
var i,m,d:integer;
begin
  if n=0 then d:=0
  else begin
    d:=-1;
    if k=0 then if nrp[p]<=n then d:=desc1(n-nrp[p],p,1);
    for i:=p+1 to 12 do if nrp[i]<=n then begin
      m:=desc1(n-nrp[i],i,k);
      if m>d then d:=m;
    end;
    if d>-1 then inc(d);
  end;
  desc1:=d;
end;
---------------------------------------------------
begin
  d:=-1;
  for i:=1 to 12 do if nrp[i]<=n then begin
    m:=desc1(n-nrp[i],i,0);
    if m>d then d:=m;
  end;
  if d<>-1 then desc:=d+1 else desc:=-1;
end;
-----------------------------------------------------
procedure marc(x,y:integer);
var i:integer;
begin
  c[x,y]:=m;inc(e[m]);
  for i:=1 to 8 do if (b[x,y]=b[x+vx[i],y+vy[i]])and(c[x+vx[i],y+vy[i]]<>m)
    then marc(x+vx[i],y+vy[i]);
end;
--------------------------------------------------------
function verp(x,y,l:integer):boolean;
var i,j:integer;v:boolean;
begin
  v:=true;
  for i:=0 to l-1 do for j:=0 to l-1 do if c[x+i,y+j]<>zm then v:=false;
  if v then for i:=0 to l-1 do for j:=0 to l-1 do c[x+i,y+j]:=0;
  verp:=v;
end;
-----------------------------------------------------
procedure unire;
var nh,i,j,k:integer;
    x,y,xh,yh,dh:array[1..100] of integer;
    xp,yp,xf,yf:integer;
procedure marc1(x,y,k:integer);
var i:integer;
begin
  c[x,y]:=k;
  for i:=1 to 8 do if (b[x,y]=b[x+vx[i],y+vy[i]])and(c[x+vx[i],y+vy[i]]<>k)
    then marc1(x+vx[i],y+vy[i],k);
end;
---------------------------------------------------------
function dist(x1,y1,x2,y2:integer):integer;
begin
  if abs(x2-x1)>abs(y2-y1) then dist:=abs(x2-x1)-1 else dist:=abs(y2-y1)-1;
end;
-------------------------------------------------------
begin
  for i:=1 to n do for j:=1 to n do if c[i,j]=zm then begin
    xp:=i;yp:=j;i:=n;j:=n; end;
  nh:=0;
  for i:=1 to n do for j:=1 to n do if (b[i,j]=d[zm])and(c[i,j]<>zm) then begin
    inc(nh);x[nh]:=i;y[nh]:=j;dh[nh]:=10;
  end;
  while nh>0 do begin
    for i:=1 to n do for j:=1 to n do if c[i,j]=zm then
      for k:=1 to nh do if dist(x[k],y[k],i,j)<dh[k] then begin
        dh[k]:=dist(x[k],y[k],i,j);xh[k]:=i;yh[k]:=j;
      end;
    j:=1;k:=1;
    for i:=1 to nh do if dh[i]<=dh[j] then j:=i else if dh[i]>dh[k] then k:=i;
    if x[j]-xh[j]<>0 then xf:=xh[j]+(x[j]-xh[j]) div abs(x[j]-xh[j]) else xf:=xh[j];
    if y[j]-yh[j]<>0 then yf:=yh[j]+(y[j]-yh[j]) div abs(y[j]-yh[j]) else yf:=yh[j];
    writeln(g,'(',xf,',',yf,'),(',x[k],',',y[k],')');
    i:=b[xf,yf];b[xf,yf]:=b[x[k],y[k]];b[x[k],y[k]]:=i;
    marc1(xp,yp,0);marc1(xp,yp,zm);
    nh:=0;
    for i:=1 to n do for j:=1 to n do if (b[i,j]=d[zm])and(c[i,j]<>zm) then begin
      inc(nh);x[nh]:=i;y[nh]:=j;dh[nh]:=10;
    end;
  end;
  for i:=1 to n do for j:=1 to n do begin
    write(g,b[i,j]:3);
    if j=n then writeln(g);
  end;
end;
-----------------------------------------------------
begin
  assign(f,'in_pl4.txt');reset(f);
  assign(g,'out.txt');rewrite(g);
  read(f,n);
  for i:=1 to n do for j:=1 to n do begin
    read(f,a[i,j]);
    b[i,j]:=desc(a[i,j]);
    write(g,b[i,j]:3);
    if j=n then writeln(g);
  end;
  writeln(g);
  for i:=0 to n+1 do begin
    b[0,i]:=0;b[n+1,i]:=0;b[i,n+1]:=0;b[i,0]:=0;
    for j:=0 to n+1 do c[i,j]:=0;
  end;
  m:=0;
  for i:=1 to n do for j:=1 to n do if c[i,j]=0 then begin
    inc(m);d[m]:=b[i,j];e[m]:=0;
    marc(i,j);
  end;
  zm:=1;
  for i:=1 to m do if (e[i]>e[zm])or((e[i]=e[zm])and(d[i]<d[zm]))
    then zm:=i;
  writeln(g,e[zm]);writeln(g,d[zm]);
  xd1:=n;xd2:=1;yd1:=n;yd2:=1;
  for i:=1 to n do for j:=1 to n do if c[i,j]=zm then begin
    if i<xd1 then xd1:=i;
    if i>xd2 then xd2:=i;
    if j<yd1 then yd1:=j;
    if j>yd2 then yd2:=j;
  end;
  writeln(g,'(',xd1,',',yd1,'),(',xd2,',',yd2,')');
  writeln(g);
  di:=e[zm];k:=c;
  if xd2-xd1<yd2-yd1 then lp:=xd2-xd1+1 else lp:=yd2-yd1+1;
  np:=0;
  while di>0 do begin
    t:=true;
    for i:=xd1 to xd2-lp+1 do for j:=yd1 to yd2-lp+1 do
      if verp(i,j,lp) then begin
        inc(np);di:=di-lp*lp;
      end;
    dec(lp);
  end;
  writeln(g,np);writeln(g);
  c:=k;
  a:=b;
  unire;
  c:=k;b:=a;
  writeln(g);
  for i:=1 to 20 do l[i]:=0;
  for i:=1 to n do for j:=1 to n do inc(l[b[i,j]]);
  j:=1;
  for i:=1 to 20 do if l[i]>l[j] then j:=i;
  zm:=0;
  for i:=1 to m do if d[i]=j then if (zm=0)or(e[zm]<e[i]) then zm:=i;
  writeln(g,d[zm]);
  unire;
  close(g);
end.
----------------------------------------------------------


(Roi dinate - Baraj Focani)
Solutie Gheorghita Valentin (Ploiesti)
program rotitele;
uses crt;
type roata=record
                 x,y,raza:real;
            end;
var a:array[1..100] of roata;
    i,n,j,k:integer;
    dist:real;
    cate,comp:array[1..100]of integer;
    b:array[1..100,1..100] of integer;
    g,f:text;
    nume:string;
    select:array[1..100]of boolean;
    ciclu:array[1..100] of integer;
    sir:array[1..100] of integer;
    sadic:integer;
    min,max:integer;
function articulatie(v:integer):boolean;
 var temp,com1,com2:array[1..100]of integer;
     i,j,k:integer;
     min,max:integer;
     test:array[1..100]of boolean;
 begin
  for i:=1 to n do
   com1[i]:=i;
  for i:=1 to n do
   for j:=1 to n do
    if b[i,j]=1 then begin
                      if com1[i]<com1[j] then begin
                                             min:=com1[i];
                                             max:=com1[j];
                                            end
                                       else begin
                                             min:=com1[j];
                                             max:=com1[i];
                                            end;
                      for k:=1 to n do
                       if com1[k]=max then com1[k]:=min;
                     end;
  for i:=1 to n do
   com2[i]:=i;
  for i:=1 to n do
   for j:=1 to n do
    if ((b[i,j]=1) and (i<>v) and (j<>v)) then begin
                      if com2[i]<com2[j] then begin
                                             min:=com2[i];
                                             max:=com2[j];
                                            end
                                       else begin
                                             min:=com2[j];
                                             max:=com2[i];
                                            end;
                      for k:=1 to n do
                       if com2[k]=max then com2[k]:=min;
                     end;
 for i:=1 to n do
  test[i]:=false;
 for i:=1 to n do
  test[com1[i]]:=true;
 min:=0;
 for i:=1 to n do
  if test[i] then min:=min+1;
 for i:=1 to n do
  test[i]:=false;
 for i:=1 to n do
  test[com2[i]]:=true;
 max:=0;
 for i:=1 to n do
  if test[i] then max:=max+1;
 if max<>min+1 then articulatie:=true
               else articulatie:=false;
 min:=com1[v];
 for i:=1 to n do
  if com1[i]<>min then com2[i]:=0;
 com2[v]:=0;
 for i:=1 to n do
  temp[i]:=0;
 for i:=1 to n do
  if com2[i]<>0 then temp[com2[i]]:=temp[com2[i]]+1;
 min:=0;
 for i:=1 to n do
  if min<temp[i] then min:=temp[i];
 sadic:=min;
end;
function test(p:integer):boolean;
 var tst:boolean;
     i:integer;
 begin
  tst:=true;
  for i:=1 to p-1 do
   if b[ciclu[i],ciclu[i+1]]=0 then tst:=false;
  test:=tst;
 end;
procedure recurs(poz:integer);
 var i:integer;
     gasit:integer;
     nr:array[1..100]of integer;
 begin
  if ((poz>3) and (b[ciclu[1],ciclu[poz-1]]=1) and (poz/2=trunc(poz/2)) and
(test(poz-1))) then
     begin
      gasit:=0;
      for i:=1 to poz-1 do
       if articulatie(ciclu[i]) then begin
                                      sir[i]:=1;
                                      nr[i]:=sadic;
                                     end
                                else begin
                                      sir[i]:=0;
                                      gasit:=ciclu[i];
                                     end;
      if gasit<>0 then for i:=1 to n do begin
                                         b[i,gasit]:=0;
                                         b[gasit,i]:=0;
                                        end;
      if gasit=0 then begin
                       gasit:=1;
                       for i:=2 to poz-1 do
                        if nr[i]>nr[gasit] then gasit:=i;
                       for i:=1 to n do begin
                                         b[i,ciclu[gasit]]:=0;
                                         b[ciclu[gasit],i]:=0;
                                        end;
                      end;
     end;
  for i:=1 to n do
   if not(select[i]) and (b[i,ciclu[poz-1]]=1) then begin
                                                   select[i]:=true;
                                                   ciclu[poz]:=i;
                                                   recurs(poz+1);
                                                   select[i]:=false;
                                                  end;
 end;
begin
 clrscr;
 write('Introduceti numele fisierului : ');
 readln(nume);
 assign(f,nume);
 reset(f);
 readln(f,n,dist);
 for i:=1 to n do
  readln(f,a[i].x,a[i].y,a[i].raza);
 close(f);
 for i:=1 to n do
  b[i,i]:=0;
 for i:=1 to n-1 do
  for j:=i+1 to n do
   if
sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y))-a[i].raza-a[j].raza<=dist
then begin
             b[i,j]:=1;
             b[j,i]:=1;
                 end
       else begin
             b[i,j]:=0;
            b[j,i]:=0;
            end;
 for i:=1 to n do
  select[i]:=false;
 for i:=1 to n do
  begin
   select[i]:=true;
   ciclu[1]:=i;
   recurs(2);
   select[i]:=false;
  end;
  writeln;
  for i:=1 to n do
   comp[i]:=i;
  for i:=1 to n do
   for j:=1 to n do
    if b[i,j]=1 then begin
                      if comp[i]<comp[j] then begin
                                             min:=comp[i];
                                             max:=comp[j];
                                            end
                                       else begin
                                             min:=comp[j];
                                             max:=comp[i];
                                            end;
                      for k:=1 to n do
                       if comp[k]=max then comp[k]:=min;
                     end;
  for i:=1 to n do
   cate[i]:=0;
  for i:=1 to n do
   cate[comp[i]]:=cate[comp[i]]+1;
  writeln('Au ramas rotile cu numerele : ');
  max:=1;
  for i:=2 to n do
   if cate[max]<cate[i] then max:=i;
  for i:=1 to n do
   if comp[i]=max then write(i,'  ');
  writeln;
  writeln('Deci au fost scoase ',n-cate[max],' roti.');
end.
